Submission #230151

# Submission time Handle Problem Language Result Execution time Memory
230151 2020-05-08T18:03:57 Z xiaowuc1 Inspector (POI13_ins) C++14
0 / 100
5000 ms 9080 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 k) {
  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 >= k) 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], l[i].t);
    latest[l[i].person] = l[i].t;
  }
  set<int> working; // working
  set<pii> preworking;
  int postworking = 0; // working
  set<pii> flexible; // not working
  set<pii> preempt; // working
  for(int i = 1; i <= n; i++) {
    if(earliest[i] <= 1e6) preworking.insert({earliest[i], i});
    else flexible.insert({earliest[i], i});
  }
  for(int i = 0; i < m; i++) {
    if(l[i].orig >= k) continue;
    // if it is their first statement, they must start working now
    if(earliest[l[i].person] == l[i].t) {
      preworking.erase({earliest[i], i});
      preempt.erase({earliest[i], i});
      working.insert(i);
    }
    while(sz(working) + postworking + sz(preempt) < l[i].work) {
      if(sz(preworking)) {
        preempt.insert(*preworking.begin());
        preworking.erase(preworking.begin());
      }
      else if(sz(flexible)) {
        preempt.insert(*flexible.begin());
        flexible.erase(flexible.begin());
      }
      else {
        return false;
      }
    }
    while(sz(working) + postworking + sz(preempt) > l[i].work) {
      if(postworking > 0) {
        postworking--;
      }
      else if(sz(preempt) && preempt.rbegin()->first > 1e6) {
        preempt.erase(*preempt.rbegin());
      }
      else if(sz(preempt) && sz(flexible)) {
        preworking.insert(*preempt.begin());
        preempt.erase(preempt.begin());
        flexible.erase(flexible.begin());
      }
      else {
        return false;
      }
    }
    // if it is their last statement, they are now post-working now
    if(latest[l[i].person] == l[i].t) {
      working.erase(i);
      postworking++;
    }
  }
  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();
}
# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1152 KB Output isn't correct
2 Incorrect 11 ms 1152 KB Output isn't correct
3 Incorrect 12 ms 1152 KB Output isn't correct
4 Incorrect 14 ms 1152 KB Output isn't correct
5 Incorrect 27 ms 1152 KB Output isn't correct
6 Incorrect 41 ms 1280 KB Output isn't correct
7 Incorrect 65 ms 1280 KB Output isn't correct
8 Incorrect 447 ms 1784 KB Output isn't correct
9 Incorrect 947 ms 2528 KB Output isn't correct
10 Incorrect 2165 ms 3832 KB Output isn't correct
11 Incorrect 2367 ms 4472 KB Output isn't correct
12 Execution timed out 5078 ms 9080 KB Time limit exceeded
13 Execution timed out 5069 ms 7544 KB Time limit exceeded