-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path10901.cpp
More file actions
95 lines (88 loc) · 2.11 KB
/
Copy path10901.cpp
File metadata and controls
95 lines (88 loc) · 2.11 KB
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
// Author: btjanaka (Bryon Tjanaka)
// Problem: (UVa) 10901
#include <bits/stdc++.h>
#define GET(x) scanf("%d", &x)
#define GED(x) scanf("%lf", &x)
typedef long long ll;
using namespace std;
// 0: arrival time
// 1: whether the car is left or right (false for left, true for right)
// 2: final time of the car
int cars[10010][3];
int main() {
int ca;
GET(ca);
bool first = true;
while (ca--) {
// input
int n, t, m;
GET(n);
GET(t);
GET(m);
char dir[10];
for (int i = 0; i < m; ++i) {
int x;
scanf("%d %s", &x, dir);
cars[i][0] = x;
cars[i][1] = strcmp(dir, "right") == 0;
}
// simulation
queue<int> left, right;
bool pos = false; // false = left, true = right
bool car_pos;
int clock = 0;
int cur_car = 0;
while (!(cur_car == m && left.empty() && right.empty())) {
// Push on any cars that arrived while the ferry was doing something else
while (cur_car < m && cars[cur_car][0] <= clock) {
if (cars[cur_car][1]) {
right.push(cur_car);
} else {
left.push(cur_car);
}
++cur_car;
}
// Just wait if both sides empty
if (left.empty() && right.empty()) {
clock = cars[cur_car][0];
continue;
}
// Make ferry move
if (!pos) {
if (!left.empty()) {
for (int i = 0; i < n && !left.empty(); ++i) {
cars[left.front()][2] = clock + t;
left.pop();
}
clock += t;
pos = true;
} else if (!right.empty()) {
clock += t;
pos = true;
}
} else {
if (!right.empty()) {
for (int i = 0; i < n && !right.empty(); ++i) {
cars[right.front()][2] = clock + t;
right.pop();
}
clock += t;
pos = false;
} else if (!left.empty()) {
clock += t;
pos = false;
};
}
}
// output
if (first) {
first = false;
} else {
putchar('\n');
}
for (int i = 0; i < m; ++i) {
printf("%d\n", cars[i][2]);
}
}
return 0;
}