QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#708626 | #8064. Gas Station | jerry2423 | WA | 1ms | 3796kb | C++17 | 3.3kb | 2024-11-04 01:15:38 | 2024-11-04 01:15:39 |
Judging History
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'