Submission #393883

#	Time	Username	Problem	Language	Result	Execution time	Memory
393883		ADMathNoob	Inspector (POI13_ins)	C++11	0 / 100	1163 ms	17412 KiB

ins

/*
 * 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];
    }
    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> add(m, 0);
      vector<int> remove(m, 0);
      for (int i = 0; i < n; i++) {
        if (first[i] != m) {
          add[first[i]] += 1;
          remove[last[i]] += 1;
        }
      }
      for (int t = 0; t < m; t++) {
        if (cnt[t] == -1) {
          continue;
        }
        while (add[t] > 0) {
          if (out_before > 0) {
            --out_before;
          } else if (in_before > 0) {
            --in_before;
          } else {
            return false;
          }
          --add[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 (remove[t] > 0) {
          ++in_after;
          --in_during;
          --remove[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;
}

• Subtask 1: 0 / 100