Submission #230149

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
230149	2020-05-08T18:00:17 Z	xiaowuc1	Inspector (POI13_ins)	C++14	0 / 100	5000 ms	24568 KB

ins

#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({1e9, 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) && 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();
}

Subtask #1

0.0 / 100.0

#	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	1280 KB	Output isn't correct
6	Incorrect	41 ms	1408 KB	Output isn't correct
7	Incorrect	64 ms	1664 KB	Output isn't correct
8	Incorrect	439 ms	4472 KB	Output isn't correct
9	Incorrect	950 ms	8076 KB	Output isn't correct
10	Incorrect	2200 ms	15060 KB	Output isn't correct
11	Incorrect	2373 ms	19920 KB	Output isn't correct
12	Execution timed out	5085 ms	21252 KB	Time limit exceeded
13	Execution timed out	5099 ms	24568 KB	Time limit exceeded