Submission #829684

#	Time	Username	Problem	Language	Result	Execution time	Memory
829684		FEDIKUS	Last supper (IOI12_supper)	C++17	100 / 100	219 ms	80240 KiB

advisor

#include "advisor.h"
#include<bits/stdc++.h>

using namespace std;
using pii = pair<int,int>;

const int maxn=1e5+10;

stack<int> occur[maxn];

int n;
set<pair<int,int> > imam;
set<int> tren;
int prosli[maxn];
int addv[2*maxn];

void ComputeAdvice(int *c, int _n, int k, int m) {
  n=_n;
  for(int i=n-1;i>=0;i--) occur[c[i]].push(i);
  for(int i=0;i<k;i++){
    int kad=n+1;
    if(!occur[i].empty()) kad=occur[i].top();
    imam.emplace(pii(-kad,i));
    tren.emplace(i);
  }
  for(int i=0;i<k;i++) prosli[i]=i;
  for(int i=0;i<n+k;i++) addv[i]=1;
  for(int i=0;i<n;i++){

    occur[c[i]].pop();
    prosli[c[i]]=k+i;

    if(tren.find(c[i])==tren.end()){      
      auto [kad,ind]=*imam.begin();
      imam.erase(*imam.begin());
      tren.erase(ind);

      addv[prosli[ind]]=0;
    }
    
    int kad=0;
    tren.emplace(c[i]);
    if(occur[c[i]].empty()) kad=n+1;
    else kad=occur[c[i]].top();
    imam.emplace(pii(-kad,c[i]));
  }

  #ifdef DEBUG
  for(int i=0;i<n+k;i++) cout<<addv[i];
  cout<<"\n";
  #endif 

  for(int i=0;i<n+k;i++) WriteAdvice(addv[i]);
}

assistant

#include "assistant.h"
#include<bits/stdc++.h>

using namespace std;

void Assist(unsigned char *a, int n, int k, int r) {
  set<int> polumrtvi;
  for(int i=0;i<k;i++) if(a[i]==0) polumrtvi.emplace(i);
  set<int> tren;
  for(int i=0;i<k;i++) tren.emplace(i);
  for(int i=0;i<n;i++){
    int req=GetRequest();
    if(tren.find(req)==tren.end()){
      
      assert(!polumrtvi.empty());
      assert(!tren.empty());

      PutBack(*polumrtvi.begin());
      tren.erase(*polumrtvi.begin());
      polumrtvi.erase(polumrtvi.begin());
    }
    tren.emplace(req);
    if(a[i+k]==0) polumrtvi.emplace(req);
  }
}

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