oj.uz

Submission #764758

# Submission time Handle Problem Language Result Execution time Memory
764758 2023-06-24T03:25:20 Z ngrace Last supper (IOI12_supper) C++14
100 / 100
 96 ms 6980 KB 
#include <bits/stdc++.h>
#include "advisor.h"
using namespace std;
#define v vector
#define ii pair<int,int>
#define fi first
#define se second

void ComputeAdvice(int *C, int N, int K, int M) {
  v<int> lastpos(N,N+1);
  v<int> nextpos(N);
  v<int> nextposk(K,N+1);
  for(int i=N-1; i>=0; i--){
    if(C[i]<K) nextposk[C[i]] = i;
    nextpos[i] = lastpos[C[i]];
    lastpos[C[i]] = i;
  }

  v<bool> scaff(N,false);
  for(int i=0; i<K; i++) scaff[i]=true;

  priority_queue<ii> pq;
  for(int i=0; i<K; i++) pq.push({nextposk[i], i});

  v<int> remov(N, -1);
  for(int i=0; i<N; i++){
    int req = C[i];
    if(!scaff[req]){
      int rem = pq.top().se;
      pq.pop();
      remov[i]=rem;
      scaff[req]=true;
      scaff[rem]=false;
    }
    pq.push({nextpos[i], req});
  }

  v<int> lastrem(N,N+1);
  v<int> nextrem(N);
  v<int> nextremk(K,N+1);
  for(int i=N-1; i>=0; i--){
    nextrem[i] = lastrem[C[i]];
    if(remov[i]==-1) continue;
    if(remov[i]<K) nextremk[remov[i]] = i;
    lastrem[remov[i]] = i;
  }

  for(int i=0; i<K; i++) WriteAdvice(nextposk[i] < nextremk[i]);
  for(int i=0; i<N; i++) WriteAdvice(nextpos[i] < nextrem[i]);
}

#include <bits/stdc++.h>
#include "assistant.h"
using namespace std;
#define v vector
#define ii pair<int,int>
#define fi first
#define se second

void Assist(unsigned char *A, int N, int K, int R) {
  set<int> active;
  set<int> passive;
  int aind=0;
  for(aind=0; aind<K; aind++){
    if(A[aind]) active.insert(aind);
    else passive.insert(aind);
  }

  for(int i=0; i<N; i++){
    int req = GetRequest();
    if(active.find(req) != active.end()) active.erase(req);
    else if(passive.find(req) != passive.end()) passive.erase(req);
    else{
      if(passive.size()>0){
        int rem = *passive.lower_bound(-1);
        passive.erase(rem);
        PutBack(rem);
      } else{
        int rem = *active.lower_bound(-1);
        active.erase(rem);
        PutBack(rem);
      }
    }
    if(A[aind]) active.insert(req);
    else passive.insert(req);
    aind++;
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 516 KB Output is correct
2 Correct 0 ms 520 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 2 ms 652 KB Output is correct
5 Correct 3 ms 676 KB Output is correct
6 Correct 4 ms 924 KB Output is correct
7 Correct 4 ms 932 KB Output is correct
8 Correct 4 ms 924 KB Output is correct
9 Correct 4 ms 924 KB Output is correct
10 Correct 4 ms 940 KB Output is correct
11 Correct 4 ms 932 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1104 KB Output is correct
2 Correct 35 ms 3148 KB Output is correct
3 Correct 89 ms 6980 KB Output is correct
4 Correct 48 ms 4496 KB Output is correct
5 Correct 55 ms 4620 KB Output is correct
6 Correct 68 ms 5092 KB Output is correct
7 Correct 82 ms 5996 KB Output is correct
8 Correct 78 ms 5636 KB Output is correct
9 Correct 47 ms 4432 KB Output is correct
10 Correct 96 ms 6792 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 5284 KB Output is correct
2 Correct 86 ms 6420 KB Output is correct
3 Correct 86 ms 6424 KB Output is correct
4 Correct 92 ms 6464 KB Output is correct
5 Correct 82 ms 6116 KB Output is correct
6 Correct 87 ms 6428 KB Output is correct
7 Correct 91 ms 6616 KB Output is correct
8 Correct 75 ms 6336 KB Output is correct
9 Correct 81 ms 6612 KB Output is correct
10 Correct 87 ms 6524 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 920 KB Output is correct
2 Correct 4 ms 960 KB Output is correct
3 Correct 3 ms 828 KB Output is correct
4 Correct 3 ms 828 KB Output is correct
5 Correct 4 ms 788 KB Output is correct
6 Correct 4 ms 820 KB Output is correct
7 Correct 4 ms 944 KB Output is correct
8 Correct 4 ms 960 KB Output is correct
9 Correct 4 ms 948 KB Output is correct
10 Correct 5 ms 1184 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 6084 KB Output is correct - 120000 bits used
2 Correct 95 ms 6312 KB Output is correct - 122000 bits used
3 Correct 91 ms 6380 KB Output is correct - 125000 bits used
4 Correct 87 ms 6432 KB Output is correct - 125000 bits used
5 Correct 87 ms 6412 KB Output is correct - 125000 bits used
6 Correct 94 ms 6332 KB Output is correct - 125000 bits used
7 Correct 89 ms 6376 KB Output is correct - 124828 bits used
8 Correct 88 ms 6408 KB Output is correct - 124910 bits used
9 Correct 86 ms 6404 KB Output is correct - 125000 bits used
10 Correct 81 ms 6300 KB Output is correct - 125000 bits used