Submission #393883

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
393883	2021-04-24T18:48:42 Z	ADMathNoob	Inspector (POI13_ins)	C++11	0 / 100	1163 ms	17412 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	204 KB	Output isn't correct
2	Incorrect	1 ms	332 KB	Output isn't correct
3	Incorrect	1 ms	332 KB	Output isn't correct
4	Incorrect	2 ms	332 KB	Output isn't correct
5	Incorrect	5 ms	460 KB	Output isn't correct
6	Incorrect	8 ms	552 KB	Output isn't correct
7	Incorrect	15 ms	752 KB	Output isn't correct
8	Incorrect	84 ms	3192 KB	Output isn't correct
9	Incorrect	195 ms	6632 KB	Output isn't correct
10	Incorrect	405 ms	12732 KB	Output isn't correct
11	Incorrect	536 ms	17412 KB	Output isn't correct
12	Incorrect	1163 ms	6880 KB	Output isn't correct
13	Incorrect	1037 ms	6728 KB	Output isn't correct