QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#708626#8064. Gas Stationjerry2423WA 1ms3796kbC++173.3kb2024-11-04 01:15:382024-11-04 01:15:39

Judging History

This is the latest submission verdict.

  • [2024-11-04 01:15:39]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3796kb
  • [2024-11-04 01:15:38]
  • Submitted

answer

#include <iostream>
#include <string>
#include <numeric>
#include <set>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <stack>
#include <cstdint>
#include <map>
#include <list>
using namespace std;

int main()
{
	int n, p;
	cin >> p >> n;
	std::vector<list<pair<int, char>>> l(p);
	std::vector<list<pair<int, char>>> r(p);

	for (int i = 0; i < n; i++)
	{
		int t, f;
		char s;
		cin >> t >> f >> s;
		for (int i = 0; i < p; i++)
		{
			for (auto it = l[i].begin(); it != l[i].end();)
			{
				if (it->first <= t)
					it = l[i].erase(it);
				else
					++it;
			}
			for (auto it = r[i].begin(); it != r[i].end();)
			{
				if (it->first <= t)
					it = r[i].erase(it);
				else
					++it;
			}
		}

		if (s == 'L')
		{
			bool added = false;
			for (int i = 0; i < p; i++)
			{
				if (l[i].empty() || (l[i].size() == 1 && l[i].front().second == 'A'))
				{
					if (l[i].empty()) {
						l[i].emplace_back(t+f, 'A');
					} else {
						l[i].emplace_back(t+f, 'B');
					}
					cout << t+f << endl;
					added = true;
					break;
				}
			}
			if (!added)
			{
				int min_idx = 0;
				for (int i = 1; i < p; i++)
				{
					if (max((int)l[i].size()-2, 0) < max((int)l[min_idx].size()-2, 0))
						min_idx = i;
				}
				// cout << l[min_idx].back() + f << endl;
				// l[min_idx].push_back(l[min_idx].back() + f);

				if (l[min_idx].size() == 1) {
					l[min_idx].emplace_back(l[min_idx].back().first+f, 'A');
				} else {
					auto p = std::prev(l[min_idx].end());
					auto pp = std::prev(p);
					if (p->second == 'A') {
						l[min_idx].emplace_back(pp->first+f, 'B');
					} else {
						if (pp->second == 'B') {
							l[min_idx].emplace_back(p->first+f, 'B');
						} else {
							if (p->first >= pp->first) {
								l[min_idx].emplace_back(p->first+f, 'A');
							} else {
								l[min_idx].emplace_back(p->first+f, 'B');
							}
						}
					}
				}
				cout << (l[min_idx].back()).first << endl;
			}
		}
		else
		{
			bool added = false;
			for (int i = 0; i < p; i++)
			{
				if (r[i].empty() || (r[i].size() == 1 && r[i].front().second == 'A'))
				{
					if (r[i].empty()) {
						r[i].emplace_back(t+f, 'A');
					} else {
						r[i].emplace_back(t+f, 'B');
					}
					cout << t+f << endl;
					added = true;
					break;
				}
			}
			if (!added)
			{
				int min_idx = 0;
				for (int i = 1; i < p; i++)
				{
					if (max((int)r[i].size()-2, 0) < max((int)r[min_idx].size()-2, 0))
						min_idx = i;
				}
				// cout << l[min_idx].back() + f << endl;
				// l[min_idx].push_back(l[min_idx].back() + f);

				if (r[min_idx].size() == 1) {
					r[min_idx].emplace_back(r[min_idx].back().first+f, 'A');
				} else {
					auto p = std::prev(r[min_idx].end());
					auto pp = std::prev(p);
					if (p->second == 'A') {
						r[min_idx].emplace_back(pp->first+f, 'B');
					} else {
						if (pp->second == 'B') {
							r[min_idx].emplace_back(p->first+f, 'B');
						} else {
							if (p->first >= pp->first) {
								r[min_idx].emplace_back(p->first+f, 'A');
							} else {
								r[min_idx].emplace_back(p->first+f, 'B');
							}
						}
					}
				}
				cout << (r[min_idx].back()).first << endl;
			}
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3592kb

input:

1 4
1 9 L
2 5 L
3 10 L
4 10 L

output:

10
7
17
27

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

1 4
1 9 L
2 9 L
3 10 L
4 10 L

output:

10
11
21
21

result:

ok 4 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 3460kb

input:

1 2
8 11 R
9 10 L

output:

19
19

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

2 10
1 10 R
2 3 R
3 10 R
4 12 R
5 1 R
6 5 R
7 10 R
10 2 R
11 7 R
13 4 R

output:

11
5
13
16
6
11
21
18
18
22

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

4 8
3 9 R
5 6 R
6 2 L
8 2 L
9 6 R
10 10 R
12 3 R
14 3 L

output:

12
11
8
10
15
20
15
17

result:

ok 8 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

2 10
1 1 L
2 7 L
3 6 L
4 10 L
5 7 L
6 1 L
7 6 L
8 1 L
9 4 L
10 1 L

output:

2
9
9
14
12
10
18
10
14
11

result:

ok 10 lines

Test #7:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

2 9
1 10 R
2 9 R
3 10 R
4 6 R
5 5 R
6 8 R
7 1 L
8 5 L
9 1 R

output:

11
11
13
10
16
18
8
13
12

result:

ok 9 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 3440kb

input:

1 9
2 2 R
6 6 R
10 4 L
12 2 R
13 5 L
17 5 R
21 3 L
23 9 R
27 9 R

output:

4
12
14
14
18
22
24
32
36

result:

ok 9 lines

Test #9:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

1 10
2 6 R
3 5 L
5 5 R
8 10 L
10 1 L
12 3 L
15 4 R
16 4 L
18 9 L
20 1 L

output:

8
8
10
18
11
15
19
20
29
21

result:

ok 10 lines

Test #10:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

2 9
1 9 R
2 1 R
3 7 R
4 5 R
5 5 R
6 7 R
7 1 R
8 1 R
9 7 R

output:

10
3
10
9
10
17
11
11
17

result:

ok 9 lines

Test #11:

score: -100
Wrong Answer
time: 1ms
memory: 3592kb

input:

2 237
8 96 R
22 85 R
36 15 R
48 47 R
56 50 R
69 30 R
79 59 R
89 53 R
97 3 R
101 76 R
105 25 R
117 38 R
119 73 R
136 83 L
151 24 R
152 67 R
157 87 R
159 20 R
168 63 L
183 32 R
198 26 R
202 24 R
206 6 R
209 99 R
222 42 L
223 31 R
240 18 R
253 92 R
254 77 R
267 38 R
269 81 R
284 31 R
288 59 R
293 89 R
...

output:

104
107
51
95
157
125
154
160
157
230
185
198
271
219
254
297
384
218
231
250
276
300
303
399
264
430
321
522
398
436
603
634
693
525
537
789
387
591
626
804
365
631
860
643
719
944
730
978
794
1042
851
1132
911
1231
994
1325
1040
596
1382
1045
1443
1100
1189
1456
1287
1467
1337
1361
1514
1585
1400
...

result:

wrong answer 7th lines differ - expected: '166', found: '154'