| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 349826 | juggernaut | Last supper (IOI12_supper) | C++14 | 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<bits/stdc++.h>
#include"advisor.h"
using namespace std;
int const MAXN=100000;
struct Color{
int id;
int np;
Color(){}
Color(int _id,int _np){
id=_id;
np=_np;
}
};
bool operator<(Color const &a,Color const &b){
return(a.np<b.np);
}
int next[MAXN];
int position[MAXN];
bool in_scaffold[MAXN];
priority_queue<Color>coda;
int solution[MAXN];
queue<int>events[MAXN];
int accumulated=0;
int counter=0;
void ComputeAdvice(int *d,int n,int k,int m){
for(int i=0;i<n;i++)position[i]=n;
for(int i=n-1;i>=0;i--)next[i]=position[d[i]],position[d[i]]=i;
for(int j=0;j<k;j++){
in_scaffold[j]=1;
coda.push(Color(j,position[j]));
}
for(int i=0;i<n;i++){
int color=d[i];
if(in_scaffold[color]){
coda.push(Color(color,next[i]));
solution[i]=-1;
events[color].push(1);
continue;
}
Color useless=coda.top();
coda.pop();
in_scaffold[useless.id]=0;
coda.push(Color(color,next[i]));
in_scaffold[color]=1;
solution[i]=useless.id;
events[useless.id].push(0);
events[color].push(1);
}
for(int j=0;j<k;j++){
if(events[j].empty()){
WriteAdvice(0);
continue;
}
if(events[j].front()==0){
events[j].pop();
WriteAdvice(0);
}else WriteAdvice(1);
}
for(int i=0;i<n;i++){
int color=d[i];
assert(events[color].front()==1);
events[color].pop();
if(events[color].empty()){
WriteAdvice(0);
continue;
}
if(events[color].front()==0){
events[color].pop();
WriteAdvice(0);
}else WriteAdvice(1);
}
}
#include<bits/stdc++.h>
#include"assistant.h"
using namespace std;
int const MAXN=100000;
bool in_the_scaffold[MAXN];
queue<int>passive;
void Assist(unsigned char *real_advice,int n,int k,int l){
for(int i=0;i<k;i++){
in_the_scaffold[i]=1;
if(real_advice[i]==0)passive.push(i);
}
for(int i=0;i<n;i++){
int color=GetRequest();
if (!in_the_scaffold[color]){
in_the_scaffold[passive.front()]=0;
in_the_scaffold[color]=1;
PutBack(passive.front());
passive.pop();
}
if(real_advice[k+i]==0)passive.push(color);
}
}