Submission #1237739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237739		guanex	Last supper (IOI12_supper)	C++20	0 / 100	157 ms	70332 KiB

advisor

#include "advisor.h"

#include<bits/stdc++.h>

using namespace std;

void ComputeAdvice(int *C, int N, int K, int M) {
  vector<int> scaff;
  vector<queue<int>> app(N);
  for(int i = 0; i < N; ++i){
    app[C[i]].push(i);
  }
  int pos[N];
  memset(pos, -1, sizeof pos);
  priority_queue<pair<int, int>> q;
  for(int i = 0; i < K; ++i){
    scaff.push_back(i);
    pos[i] = i;
    if((int)app[i].size() == 0){
      q.push({1e6, i});
    }else{
      q.push({app[i].front(), i});
    }
  }
  vector<int> out;
  for(int i = 0; i < N; ++i){
    int req = C[i];
    if(pos[req] == -1){
      pair<int, int> far = q.top();
      q.pop();
      int npos = pos[far.second];
      out.push_back(npos);
      pos[far.second] = -1;
      pos[req] = npos;
      while((int)app[req].size() > 0 && app[req].front() <= i){
        app[req].pop();
      }
      if((int)app[req].size() == 0){
        q.push({1e6, req});
      }else{
        q.push({app[req].front(), i});
      }
    }else{
      while((int)app[req].size() > 0 && app[req].front() <= i){
        app[req].pop();
      }
      if((int)app[req].size() == 0){
        q.push({1e6, req});
      }else{
        q.push({app[req].front(), i});
      }
    }
  }
  int bits = 0;
  int pot = 1;
  for(int i = 0; i < 30; ++i){
    if(pot >= K){
      bits = i;
      break;
    }
    pot *= 2;
  }
  for(auto e:out){
    for(int i = 0; i <= bits; ++i){
      if(e & (1 << i)){
        WriteAdvice(1);
        //cout << 1 << " ";
      }else{
        WriteAdvice(0);
        //cout << 0 << " ";
      }
    }
  }
  //cout << endl;
}

assistant

#include "assistant.h"

#include<bits/stdc++.h>

using namespace std;

void Assist(unsigned char *A, int N, int K, int R) {
  int bits = 0;
  int pot = 1;
  for(int i = 0; i < 30; ++i){
    if(pot >= K){
      bits = i;
      break;
    }
    pot *= 2;
  }
  int i = 0;
  vector<int> out;
  for(i; i < R; i += bits+1){
    int num = 0;
    int po = 1;
    for(int j = i; j <= i + bits; ++j){
      if(A[j]){
        num += po;
      }
      po *= 2;
    }
    out.push_back(num);
  }
  //cout << "nice" << endl;
  vector<int> scaff;
  int pos[N];
  memset(pos, -1, sizeof pos);
  for(int i = 0; i < K; ++i){
    scaff.push_back(i);
    pos[i] = i;
  }
  int j = 0;
  for (i = 0; i < N; i++) {
    int req = GetRequest();
    if(pos[req] != -1){
      continue;
    }
    int outnum = scaff[out[j]];
    PutBack(outnum);
    scaff[out[j]] = req;
    pos[req] = out[j];
    pos[outnum] = -1;
    j++;
  }

}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 35
• Subtask 5: 0 / 39