Submission #113791

#	Time	Username	Problem	Language	Result	Execution time	Memory
113791		nxteru	Last supper (IOI12_supper)	C++14	0 / 100	37 ms	10208 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
int n,k,pr[200005],nx[200005],co[200005],nex[200005],p[200005],ex[200005];
void ComputeAdvice(int *C, int N, int K, int M) {
	n=N,k=K;
	for(int i=0;i<n;i++)p[i]=n;
	for(int i=n-1;i>=0;i--){
		nex[i]=p[C[i]];
		p[C[i]]=i;
	}
	nx[0]=1;
	for(int i=1;i<=k;i++){
		co[i]=i-1;
		pr[i]=i-1;
		nx[i]=i+1;
	}
	pr[k+1]=k;
	priority_queue<P>d;
	for(int i=0;i<k;i++)d.push(P(p[i],i)),ex[i]=i+1;
	for(int i=0;i<n;i++){
		int c=C[i];
		if(ex[c]!=0){
			int x=ex[c],a=pr[x],b=nx[x],y=pr[k+1];
			nx[a]=b;
			pr[b]=a;
			nx[y]=x;
			pr[x]=y;
			nx[x]=k+1;
			pr[k+1]=x;
		}else{
			while(1){
				int y=d.top().S;
				d.pop();
				if(ex[y]==0)continue;
				int z=pr[k+1];
				while(co[z]!=y){
					z=pr[z];
					WriteAdvice(0);
				}
				WriteAdvice(1);
				int a=pr[z],b=nx[z],f=pr[k+1];
				pr[b]=a;
				nx[a]=b;
				ex[y]=0;
				ex[c]=z;
				nx[f]=z;
				pr[z]=f;
				nx[z]=k+1;
				pr[k+1]=z;
				co[z]=c;
				break;
			}
		}
		d.push(P(nex[i],c));
	}
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
int na,ka,l,pra[200005],nxa[200005],coa[200005],exb[200005];
void Assist(unsigned char *A, int N, int K, int R) {
	na=N,ka=K;
	nxa[0]=1;
	for(int i=1;i<=ka;i++){
		coa[i]=i-1;
		pra[i]=i-1;
		nxa[i]=i+1;
	}
	pra[ka+1]=ka;
	for(int i=0;i<ka;i++)exb[i]=i+1;
	for(int i=0;i<na;i++){
		int c=GetRequest();
		if(exb[c]!=0){
			int x=exb[c],a=pra[x],b=nxa[x],y=pra[ka+1];
			nxa[a]=b;
			pra[b]=a;
			nxa[y]=x;
			pra[x]=y;
			nxa[x]=ka+1;
			pra[ka+1]=x;
		}else{
				int z=pra[ka+1];
				while(A[l]==0){
					l++;
					z=pra[z];
				}
				l++;
				PutBack(coa[z]);
				int a=pra[z],b=nxa[z],f=pra[ka+1];
				pra[b]=a;
				nxa[a]=b;
				exb[coa[z]]=0;
				exb[c]=z;
				nxa[f]=z;
				pra[z]=f;
				nxa[z]=ka+1;
				pra[ka+1]=z;
				coa[z]=c;
		}
	}
}

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