Submission #280491

#	Time	Username	Problem	Language	Result	Execution time	Memory
280491		amiratou	Last supper (IOI12_supper)	C++14	0 / 100	314 ms	24976 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(x) (int)(x.size())
typedef pair<int,int> ii;
const int INF = (int)(1e9);

vector<int> vec[100005];
int occ[100005];
set<ii,greater<ii> > myset;
int pos[100005],in[100005];

void ComputeAdvice(int *C, int N, int K, int M) {
	int l=31-__builtin_clz(K+1)+1;
	for (int i = 0; i < N; ++i)
	{
		occ[i]=sz(vec[C[i]]);
		vec[C[i]].push_back(i);
	}
	for (int i = 0; i < K; ++i){
		pos[i]=i,in[i]=1;
		if(!sz(vec[i]))myset.insert({INF,i});
		else myset.insert({vec[i][0],i});
	}
	vector<int> code;
	for (int i = 0; i < N; ++i)
	{
		if(in[C[i]]){
			myset.erase({i,C[i]});
			if((occ[i]+1)<sz(vec[C[i]]))myset.insert({vec[C[i]][occ[i]+1],C[i]});
			else myset.insert({INF,C[i]});
		}
		else{
			ii h=*myset.begin();
			myset.erase(myset.begin());
			code.push_back(h.se);
			in[h.se]=0,in[C[i]]=1;
			if((occ[i]+1)<sz(vec[C[i]]))myset.insert({vec[C[i]][occ[i]+1],C[i]});
			else myset.insert({INF,C[i]});
			pos[C[i]]=pos[h.se];
		}
		/*for(auto it:myset){
			cerr<<it.fi<<","<<it.se<<"\n";
		}
		cerr<<"--------\n";*/
	}
	//cerr<<l<<" ";
	for(auto it:code){
		//cerr<<it<<" ";
		for (int i = 0; i < l; ++i){
			//cerr<<((it>>i)&1)<<" ";
			WriteAdvice((it>>i)&1);
		}
		//cerr<<"\n";
	}
	//cerr<<"\n";
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(x) (int)(x.size())
typedef pair<int,int> ii;
const int INF = (int)(1e9);

int tab[100005],here[100005];

void Assist(unsigned char *A, int N, int K, int R) {
	int l=31-__builtin_clz(K+1)+1;
	for (int i = 0; i < K; ++i)
		tab[i]=i,here[i]=1;
	assert(!(R%l));
	vector<int> vec;
	for (int i = 0; i < R; i+=l)
	{
		int nb=0;
		for (int j = 0; j < l; ++j)
			if(A[i+j]=='1')nb+=(1<<j);
		vec.push_back(nb);
	}
	int idx=0;
	for (int i = 0; i < N; ++i)
	{
		int h=GetRequest();
		if(!here[h]){
			assert(idx<sz(vec));
			here[vec[idx]]=0;
			here[h]=1;
			PutBack(vec[idx]),idx++;
		}
	}
}

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