답안 #230156

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230156 2020-05-08T18:24:46 Z xiaowuc1 Inspector (POI13_ins) C++14
92 / 100
5000 ms 6628 KB
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_set>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define derr if(1) cerr
typedef vector<int> vi;
// END NO SAD

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<ll>> matrix;

typedef pair<int, pii> state;

struct statement {
  int t, person, work, orig;
  bool operator<(statement& s) {
    return t < s.t;
  }
};

int n, m;
statement l[100005];

int earliest[100005];
int latest[100005];
bool can(int thresh) {
  memset(earliest, 1, sizeof(earliest));
  memset(latest, -1, sizeof(latest));
  int lastt = -1;
  int lastclaim = -1;
  // first check that everyone claims the same number of people
  for(int i = 0; i < m; i++) {
    if(l[i].orig >= thresh) continue;
    if(l[i].work > n) return false;
    if(l[i].t == lastt && l[i].work != lastclaim) return false;
    lastt = l[i].t;
    lastclaim = l[i].work;
    earliest[l[i].person] = min(earliest[l[i].person], i);
    latest[l[i].person] = i;
  }
  set<int> working; // working
  set<pii> preworking;
  int postworking = 0; // working
  int flexible = 0;
  set<pii> preempt; // working
  for(int i = 1; i <= n; i++) {
    if(earliest[i] <= 1e6) preworking.insert({earliest[i], i});
    else flexible++;
  }
  for(int i = 0; i < m;) {
    if(l[i].orig >= thresh) {
      i++;
      continue;
    }
    int j = i;
    while(j < m && l[i].t == l[j].t) j++;
    for(int k = i; k < j; k++) {
      if(l[k].orig >= thresh) continue;
      // if it is their first statement, they must start working now
      if(earliest[l[k].person] == k) {
        int amt = preworking.erase({earliest[l[k].person], l[k].person});
        amt += preempt.erase({earliest[l[k].person], l[k].person});
        assert(amt == 1);
        working.insert(l[k].person);
      }
    }
    while(sz(working) + postworking + sz(preempt) < l[i].work) {
      if(sz(preworking)) {
        preempt.insert(*preworking.begin());
        preworking.erase(preworking.begin());
      }
      else if(flexible) {
        postworking++;
        flexible--;
      }
      else {
        return false;
      }
    }
    while(sz(working) + postworking + sz(preempt) > l[i].work) {
      if(postworking > 0) {
        postworking--;
      }
      else if(sz(preempt) && flexible) {
        preworking.insert(*preempt.begin());
        preempt.erase(preempt.begin());
        flexible--;
      }
      else {
        return false;
      }
    }
    for(int k = i; k < j; k++) {
      if(l[k].orig >= thresh) continue;
      // if it is their last statement, they are post-working now
      if(latest[l[k].person] == k) {
        assert(working.count(l[k].person));
        working.erase(l[k].person);
        postworking++;
      }
    }
    i = j;
  }
  return true;
}

void rsolve() {
  cin >> n >> m;
  for(int i = 0; i < m; i++) {
    l[i].orig = i;
    cin >> l[i].t >> l[i].person >> l[i].work;
    l[i].work++;
  }
  sort(l, l+m);
  int lhs = 0;
  int rhs = m;
  while(lhs < rhs) {
    int mid = (lhs+rhs+1)/2;
    if(can(mid)) lhs = mid;
    else rhs = mid - 1;
  }
  cout << lhs << "\n";
}

void solve() {
  int t;
  cin >> t;
  while(t--) rsolve();
}
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1152 KB Output is correct
2 Correct 11 ms 1152 KB Output is correct
3 Correct 12 ms 1152 KB Output is correct
4 Correct 15 ms 1280 KB Output is correct
5 Correct 25 ms 1152 KB Output is correct
6 Correct 41 ms 1188 KB Output is correct
7 Correct 60 ms 1280 KB Output is correct
8 Correct 381 ms 1784 KB Output is correct
9 Correct 855 ms 2424 KB Output is correct
10 Correct 2071 ms 3936 KB Output is correct
11 Correct 2347 ms 3576 KB Output is correct
12 Execution timed out 5031 ms 6280 KB Time limit exceeded
13 Correct 4650 ms 6628 KB Output is correct