UVA/10172.cpp at master · johan-smc/UVA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <vector>
#include <queue>
#include <bitset>
#include <stack>

#define foi( i , k , n ) for( int i = k ;  i <  n ; ++i )
using namespace std;

void print(vector< queue<int> > a)
{
  foi( i , 0 , a.size() )
  {
    cout<<i<<" -- ";
    while( !a[i].empty() )
    {
      cout<<a[i].front()<<" ";
      a[i].pop();
    }
    cout<<endl;
  }
}

void print( stack<int> q)
{
  while( !q.empty() )
  {
    cout<<q.top()<<" ";
    q.pop();
  }
  cout<<endl;
}
int main()
{
  int t;
  scanf("%d",&t);
  while( t-- )
  {
    int n,c,m;
    scanf("%d%d%d",&n,&c,&m);
    int q,cc,time=0;
    std::vector< queue<int> > v(n,queue<int>());
    bitset<105> ps;
    foi( i , 0 , n )
    {
      scanf("%d",&q);
      foi( j , 0 , q)
      {
        ps[i]=true;
        scanf("%d",&cc);
        v[i].push(cc-1);
      }
    }
    int pos=0;
    stack<int> mov;
    while( ps.any() || !mov.empty())
    {
      // cout<<"---------------------------"<<endl;
      // cout<<ps<<endl;
      // print(v);
      // cout<<".. "<< pos << " ...";
      // print(mov);
      // cout<<"t "<<time<<endl;
      while( !mov.empty()  && v[pos].size() < m)
      {
        if( mov.top() == pos )
          mov.pop();
        else
        {
            v[pos].push(mov.top());
            mov.pop();
        }
        ++time;
      }
      while( !mov.empty() && mov.top() == pos )
      {
        mov.pop();
        ++time;
      }
      while( mov.size()  <  c && !v[pos].empty() )
      {
        mov.push(v[pos].front());
        v[pos].pop();
        ++time;
      }
      if( v[pos].empty() )
        ps[pos]=false;
      pos++;
      pos%=n;
      time+=2;
      // cout<<"t "<<time<<endl;
      // cout<<".. "<< pos << " ...";
      // print(mov);
      // print(v);
      // cout<<ps<<endl;
      // cout<<"---------------------------"<<endl;
    }
    printf("%d\n",time-2 );
  }
  return 0;
}