/*
* author: ADMathNoob
* created: 04/22/21 14:39:48
* problem: https://www.acmicpc.net/problem/8242
*/
/*
g++ boj_8242.cpp -D_DEBUG -std=c++11 -Wl,--stack=268435456 -Wall -Wfatal-errors -ggdb && gdb a
g++ boj_8242.cpp -D_DEBUG -std=c++11 -Wl,--stack=268435456 -O3 -Wall -Wfatal-errors
Try to avoid O(n log^2(n)) per case?
pessimistic
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n, m;
cin >> n >> m;
vector<int> when(m);
vector<int> who(m);
vector<int> others(m);
for (int j = 0; j < m; j++) {
cin >> when[j] >> who[j] >> others[j];
--when[j];
--who[j];
assert(0 <= when[j] && when[j] < m);
assert(0 <= who[j] && who[j] < n);
}
auto Works = [&](int mid) -> bool {
vector<int> cnt(m, -1);
vector<int> first(n, m);
vector<int> last(n, -1);
// check that the claims are consistent for each point in time
for (int j = 0; j < mid; j++) {
int t = when[j];
if (cnt[t] != -1 && cnt[t] != others[j] + 1) {
return false;
}
cnt[t] = others[j] + 1;
int i = who[j];
first[i] = min(first[i], t);
last[i] = max(last[i], t);
}
// the "shift" is the time each person must be in
int extras = count(first.begin(), first.end(), m);
int in_during = 0; // currently in shift
int out_before = n - extras; // can join whenever
int in_before = 0; // can be swapped out if required
int in_after = 0; // can leave whenever
vector<int> start(m, 0); // number of people that start their shift
vector<int> end(m, 0); // number of people that end their shift
for (int i = 0; i < n; i++) {
if (first[i] != m) {
start[first[i]] += 1;
end[last[i]] += 1;
}
}
for (int t = 0; t < m; t++) {
if (cnt[t] == -1) {
assert(start[t] == 0 && end[t] == 0);
continue;
}
while (start[t] > 0) {
if (out_before > 0) {
--out_before;
} else {
assert(in_before > 0);
--in_before;
}
--start[t];
++in_during;
}
while (in_before + in_during + in_after < cnt[t]) {
if (out_before > 0) {
--out_before;
++in_before;
} else if (extras > 0) {
--extras;
++in_after;
} else {
return false;
}
}
while (in_before + in_during + in_after > cnt[t]) {
if (in_after > 0) {
--in_after;
} else if (in_before > 0 && extras > 0) {
--in_before;
++out_before;
--extras;
} else {
return false;
}
}
while (end[t] > 0) {
++in_after;
--in_during;
--end[t];
}
}
return true;
};
int low = 0, high = m;
while (low < high) {
int mid = (low + high + 1) >> 1;
if (Works(mid)) {
low = mid;
} else {
high = mid - 1;
}
}
cout << low << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Incorrect |
4 ms |
332 KB |
Output isn't correct |
| 6 |
Incorrect |
8 ms |
352 KB |
Output isn't correct |
| 7 |
Incorrect |
16 ms |
384 KB |
Output isn't correct |
| 8 |
Incorrect |
82 ms |
644 KB |
Output isn't correct |
| 9 |
Incorrect |
190 ms |
1048 KB |
Output isn't correct |
| 10 |
Incorrect |
389 ms |
1704 KB |
Output isn't correct |
| 11 |
Incorrect |
508 ms |
1892 KB |
Output isn't correct |
| 12 |
Incorrect |
1116 ms |
3756 KB |
Output isn't correct |
| 13 |
Incorrect |
986 ms |
3584 KB |
Output isn't correct |
