UVA/10901.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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <queue>
#include <vector>

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

int main()
{
  int ca;
  scanf("%d",&ca);
  while(ca--)
  {
    int n,t,m,min;
    string dir;
    queue< pair< int , int > > left,right;
    scanf("%d%d%d",&n,&t,&m);
    foi( i , 0 , m )
    {
      scanf("%d",&min);
      cin>>dir;
      if(dir=="left")
      {
        left.push(make_pair(min,i));
      }
      else if( dir =="right")
      {
        right.push(make_pair(min,i));
      }
    }
    int time=0;
    bool pos=true;
    std::vector<int> print(m);
    while( !left.empty() || !right.empty() )
    {

      int c=0;
    // cout<<" -- "<<c<<" "<<pos <<" " <<time<<" " <<left.size() <<" " <<right.size() <<endl;
      if( pos   )
      {
        if( left.empty() )
        {
          if( !right.empty())
          {
            if(  time+t > right.front().first+t)
              time+=t;
            else
              time=right.front().first+t;
          }
          pos=false;
          continue;
        }
        if( left.front().first <= time)
        {
          while( !left.empty() && left.front().first <= time && c < n)
          {
            print[left.front().second]=(time+t);
            left.pop();
            c++;
          }
          time+=t;
        }
        else if( right.empty() || left.front().first <= right.front().first)
        {
          // cout<<"1a"<<endl;
          time=left.front().first;
          pos=false;
        }
        else
        {
          // cout<<"2a "<<right.front().first<<" "<<t<<endl;
          if( time+t < right.front().first+t)
            time=right.front().first+t;
          else
            time+=t;
        }
          pos=!pos;
      }
      else
      {
        if( right.empty() )
        {
          if( !left.empty())
          {
            if(  time+t > left.front().first+t)
              time+=t;
            else
              time=left.front().first+t;
            }
          pos=true;
          continue;
        }
        if(  right.front().first <= time )
        {
          while( !right.empty() && right.front().first <= time && c < n)
          {
            print[right.front().second]=(time+t);
            right.pop();
            c++;
          }
          time+=t;
        }
        else if( left.empty() ||(right.front().first <= left.front().first) )
        {
          // cout<<"1b "<<endl;
          time=right.front().first;
          pos=true;
        }
        else
        {
          // cout<<"2b"<<endl;
          if( time+t < left.front().first+t )
            time=left.front().first+t;
          else
            time+=t;
        }
        pos=!pos;
      }
      // cout<<m<<" "<<print.size() <<endl;
    }
    foi( i , 0 , print.size() )
    printf("%d\n",print[i] );

    if( ca!= 0 )
      printf("\n");
  }

  return 0;
}