Submission #764758

#	Time	Username	Problem	Language	Result	Execution time	Memory
764758		ngrace	Last supper (IOI12_supper)	C++14	100 / 100	96 ms	6980 KiB

advisor

#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]);
}

assistant

#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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 35 / 35
• Subtask 5: 39 / 39