Submission #393889

# Submission time Handle Problem Language Result Execution time Memory
393889 2021-04-24T18:56:38 Z ADMathNoob Inspector (POI13_ins) C++11
0 / 100
1116 ms 3756 KB
/*
 * 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