Submission #1183623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183623		hyakup	Last supper (IOI12_supper)	C++20	100 / 100	130 ms	70728 KiB

advisor

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

using pii = pair<int, int>;

void ComputeAdvice( int *v, int n, int k, int m ){
  vector<queue<int>> occur(n);
  for( int i = 0; i < n; i++ ) occur[v[i]].push(i);
  for( int i = 0; i < n; i++ ) occur[i].push(n);

  vector<int> advice( n + k ), marc(n, -1);
  int cur = 0;

  set<pii> s;
  for( int i = 0; i < k; i++ ) s.insert(pii( occur[i].front(), i )), marc[i] = cur++;

  auto find =  [&]( set<pii> &s, pii p ){ return s.find(p) != s.end(); };

  for( int i = 0; i < n; i++ ){
    if( marc[v[i]] != -1 ){
      advice[marc[v[i]]] = 1;
      s.erase({ occur[v[i]].front(), v[i] });
    }
    else{
      advice[marc[s.rbegin()->second]] = 0;
      marc[s.rbegin()->second] = -1;
      s.erase(prev(s.end()));
    }

    occur[v[i]].pop();
    marc[v[i]] = cur++;
    s.insert({ occur[v[i]].front(), v[i] });
  }

  for( auto [x, id] : s ) advice[marc[id]] = 1;

  for( int x : advice ) WriteAdvice(x);
}

assistant

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

void Assist(unsigned char *a, int n, int k, int r ) {
  set<int> s[2];
  vector<int> marc(n);
  int cur = 0;
  for(; cur < k; cur++ ){
    marc[cur] = a[cur];
    s[a[cur]].insert(cur);
  }

  auto find = [&]( set<int> &s, int x ){ return s.find(x) != s.end(); };

  for( int i = 0; i < n; i++ ){
    int cor = GetRequest();
    if( find(s[marc[cor]], cor) ) s[marc[cor]].erase(cor);
    else{
      int tirar = *s[0].begin(); s[0].erase(s[0].begin());
      PutBack(tirar);
    }
    marc[cor] = a[cur++];
    s[marc[cor]].insert(cor);
  }
}

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