Submission #137454

#	Time	Username	Problem	Language	Result	Execution time	Memory
137454		jangwonyoung	Last supper (IOI12_supper)	C++14	100 / 100	188 ms	13296 KiB

advisor

#include "advisor.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
int n,k;
int prv[200001];
int nxt[200001];
int c[200001];
int in[200001];
bool die[200001];
set<pair<int,int> >v;
void ComputeAdvice(int *C, int N, int K, int M) {
	n=N;k=K;
	for(int i=1; i<=n ;i++){
		c[k+i]=C[i-1]+1;
		prv[i]=n+k+1;
	}
	for(int i=1; i<=k ;i++) c[i]=i;
	for(int i=n+k; i>=1 ;i--){
		nxt[i]=prv[c[i]];
		if(i<=k) v.insert({nxt[i],i});
		prv[c[i]]=i;
		if(i<=k) in[i]=true;
	}
	for(int i=k+1; i<=n+k ;i++){
		if(!in[c[i]]){
			auto it=v.end();--it;
			die[it->se]=true;
			in[c[it->se]]=0;
			v.erase(it);
		}
		else{
			v.erase({i,in[c[i]]});
		}
		v.insert({nxt[i],i});
		in[c[i]]=i;
	}
	for(int i=1; i<=n+k ;i++){
		WriteAdvice(die[i]);
	}
}

assistant

#include "assistant.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
int n,k;
bool s[200001];
set<pair<int,int> >bin[2];
void Assist(unsigned char *A, int N, int K, int R){
	n=N;k=K;
	for(int i=1; i<=n+k ;i++) s[i]=!A[i-1];
	for(int i=1; i<=k ;i++){
		bin[s[i]].insert({i,i});
	}
	for(int i=k+1; i<=n+k ;i++){
		int cur=GetRequest()+1;
		auto it=bin[1].lower_bound({cur,0});
		if(it==bin[1].end() || it->fi!=cur){
			it=bin[0].begin();
			PutBack(it->fi-1);
			int duh=it->se;
			bin[0].erase(it);
			bin[s[i]].insert({cur,duh});
		}
		else{
			auto tmp=*it;
			bin[1].erase(it);
			bin[s[i]].insert(tmp);
		}
	}
}

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