oj.uz

Submission #219645

# Submission time Handle Problem Language Result Execution time Memory
219645 2020-04-05T21:11:41 Z MarcoMeijer Last supper (IOI12_supper) C++14
100 / 100
 343 ms 153328 KB 
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()

const int MX = 1e5;
queue<int> nxt[MX];
set<int> onShelf;
priority_queue<ii> pq;
map<int, int> last;
vi ans;

void ComputeAdvice(int *C, int N, int K, int M) {
  RE(i,N) while(!nxt[i].empty()) nxt[i].pop();
  onShelf.clear();
  while(!pq.empty()) pq.pop();
  ans.clear();

  RE(i,N) nxt[C[i]].push(i);
  RE(i,N) nxt[i].push(N);
  ans.assign(K+N,0);
  RE(i,K) {
    onShelf.insert(i);
    pq.push({nxt[i].front(), i});
    last[i] = i;
  }
  RE(i,N) {
    nxt[C[i]].pop();
    last[C[i]] = K+i;
    if(onShelf.count(C[i])) {
      pq.push({nxt[C[i]].front(), C[i]});
      continue;
    }
    while(1) {
      ii p = pq.top(); pq.pop();
      if(!onShelf.count(p.se)) continue;
      ans[last[p.second]] = 1;
      onShelf.erase(p.se);
      break;
    }
    pq.push({nxt[C[i]].front(), C[i]});
    onShelf.insert(C[i]);
  }
  for(int i:ans) WriteAdvice(i);
}

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()

set<int> OnShelf;
queue<int> rem;

void Assist(unsigned char *A, int N, int K, int R) {
  OnShelf.clear();
  while(!rem.empty()) rem.pop();

  RE(i,K) {
    OnShelf.insert(i);
    if(A[i]) rem.push(i);
  }
  RE(i,N) {
    int req = GetRequest();
    if(!OnShelf.count(req)) {
      PutBack(rem.front());
      OnShelf.erase(rem.front()); rem.pop();
      OnShelf.insert(req);
    }
    if(A[K+i]) rem.push(req);
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 134912 KB Output is correct
2 Correct 55 ms 135424 KB Output is correct
3 Correct 64 ms 135920 KB Output is correct
4 Correct 60 ms 135408 KB Output is correct
5 Correct 64 ms 135920 KB Output is correct
6 Correct 68 ms 135920 KB Output is correct
7 Correct 59 ms 135936 KB Output is correct
8 Correct 62 ms 136176 KB Output is correct
9 Correct 89 ms 135920 KB Output is correct
10 Correct 73 ms 136176 KB Output is correct
11 Correct 62 ms 135920 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 136528 KB Output is correct
2 Correct 144 ms 140008 KB Output is correct
3 Correct 343 ms 153048 KB Output is correct
4 Correct 247 ms 145904 KB Output is correct
5 Correct 247 ms 145904 KB Output is correct
6 Correct 300 ms 147176 KB Output is correct
7 Correct 301 ms 149464 KB Output is correct
8 Correct 276 ms 150496 KB Output is correct
9 Correct 185 ms 140272 KB Output is correct
10 Correct 318 ms 151256 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 146656 KB Output is correct
2 Correct 330 ms 150744 KB Output is correct
3 Correct 301 ms 150488 KB Output is correct
4 Correct 310 ms 150528 KB Output is correct
5 Correct 251 ms 147928 KB Output is correct
6 Correct 318 ms 150768 KB Output is correct
7 Correct 299 ms 150232 KB Output is correct
8 Correct 331 ms 153328 KB Output is correct
9 Correct 248 ms 148440 KB Output is correct
10 Correct 312 ms 150720 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 135920 KB Output is correct
2 Correct 65 ms 136040 KB Output is correct
3 Correct 61 ms 135680 KB Output is correct
4 Correct 61 ms 135920 KB Output is correct
5 Correct 66 ms 135920 KB Output is correct
6 Correct 63 ms 135920 KB Output is correct
7 Correct 62 ms 135920 KB Output is correct
8 Correct 62 ms 135920 KB Output is correct
9 Correct 64 ms 136176 KB Output is correct
10 Correct 66 ms 136448 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 148696 KB Output is correct - 120000 bits used
2 Correct 317 ms 149736 KB Output is correct - 122000 bits used
3 Correct 299 ms 150232 KB Output is correct - 125000 bits used
4 Correct 317 ms 150504 KB Output is correct - 125000 bits used
5 Correct 287 ms 149976 KB Output is correct - 125000 bits used
6 Correct 317 ms 150168 KB Output is correct - 125000 bits used
7 Correct 304 ms 149976 KB Output is correct - 124828 bits used
8 Correct 317 ms 150744 KB Output is correct - 124910 bits used
9 Correct 295 ms 150232 KB Output is correct - 125000 bits used
10 Correct 311 ms 153064 KB Output is correct - 125000 bits used