| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 744089 | boyliguanhan | Last supper (IOI12_supper) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "advisor.h"
#include <map>
#include <vector>
#include <stack>
#include <algorithm>
#include <stdio.h>
using namespace std;
int where[1000005];
int Next[1000005];
vector < int > when[100005];
map < int , int > how;
void ComputeAdvice(int *C, int N, int K, int M)
{
int t=0,now=1,xx,i,j;
while(now<K)
{
now*=2;
t++;
}
for(i=0;i<N;i++) when[C[i]].push_back(i);
for(i=0;i<N;i++) when[i].push_back(i+N);
for(i=0;i<N;i++) Next[i]=*upper_bound(when[C[i]].begin(),when[C[i]].end(),i);
for(i=0;i<K;i++)
{
where[i]=i;
how[when[i][0]]=i;
}
for(i=K;i<N;i++) where[i]=-1;
for(i=0;i<N;i++)
{
if(how.find(i)!=how.end()) how.erase(i);
if(where[C[i]]==-1)
{
xx=where[prev(how.end())->second];
for(j=0;j<t;j++)
{
if(xx&(1<<j)) WriteAdvice(1);
else WriteAdvice(0);
}
where[C[i]]=xx;
where[prev(how.end())->second]=-1;
how.erase(prev(how.end()));
} else {
for(j = 0; j < t; j++)
if(K&(1<<j)) WriteAdvice(1);
else WriteAdvice(0);
}
how[Next[i]]=C[i];
}
}