답안 #393889

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
393889	2021-04-24T18:56:38 Z	ADMathNoob	Inspector (POI13_ins)	C++11	0 / 100	1116 ms	3756 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];
      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;
}

Subtask #1

0.0 / 100.0

#	결과	실행 시간	메모리	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