Submission #295486

#	Time	Username	Problem	Language	Result	Execution time	Memory
295486		rqi	Last supper (IOI12_supper)	C++14	0 / 100	88 ms	8096 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;

#define mp make_pair
#define f first
#define s second

const int mx = 200005;

int col[mx];

int nex[mx]; //next needed
int curpos[mx]; //current position of a color

bool getK[mx]; //does this index get kicked off before needed again

bool inScaf[mx]; //is this color in the scaffold
queue<int> unq; //indices of C that have not been queried yet

void ComputeAdvice(int *C, int N, int K, int M) {

	// cout << "B1" << "\n";
	// cout.flush();
	for(int i = 0; i < N; i++){
		col[i+K] = C[i];
	}
	for(int i = 0; i < K; i++){
		col[i] = i;
	}


	for(int i = 0; i < N; i++){
		curpos[i] = N+K;
	}
	for(int i = N-1; i >= -K; i--){
		nex[i+K] = curpos[col[i+K]];
		curpos[col[i+K]] = i+K;
		//cout << i+K << " " << nex[i+K] << "\n";
	}
	// cout << "B2" << "\n";
	// cout.flush();
	priority_queue<pi> pq; //when needed again, index+K
	for(int i = 0; i < K; i++){
		pq.push(mp(nex[i-K+K], i-K+K));
		inScaf[i] = 1;
	}
	for(int i = 0; i < N; i++){
		if(inScaf[col[i+K]]) continue;
		pi a = pq.top();
		//cout << i << " " << a.f << " " << a.s << "\n";
		pq.pop();
		getK[a.s] = 1; //got kicked off
		pq.push(mp(nex[i+K], i+K));
		//cout << col[i+K] << " " << col[a.s] << "\n";
		inScaf[col[i+K]] = 1;
		inScaf[col[a.s]] = 0;
	}
	// cout << "B3" << "\n";
	// cout.flush();
	for(int i = -K; i < N; i++){
		WriteAdvice(getK[i+K]);
		//cout << i+K << " " << col[i+K] << " " << nex[i+K] << " " << getK[i+K] << "\n";
	}

	for(int i = 0; i < N; i++){
		if(i < K) inScaf[i] = 1;
		else inScaf[i] = 0;
	}
	for(int i = 0; i < K; i++){
		unq.push(i-K+K);
	}
	
	// cout << "B4" << "\n";
	// cout.flush();
	for(int i = 0; i < N; i++){
		if(inScaf[col[i+K]]) continue; //do nothing
		inScaf[col[i+K]] = 1;
		while(true){
			int a = unq.front();
			unq.pop();
			if(getK[a]){
				inScaf[col[a]] = 0;
				break;
			}
		}
		unq.push(i+K);
	}

	// cout << "B5" << "\n";
	// cout.flush();
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;

const int mx = 200005;

int col2[mx];
bool getK2[mx]; //does this index get kicked off before needed again

bool inScaf2[mx]; //is this col2or in the scaffold
queue<int> unq2; //indices of C that have not been queried yet

void Assist(unsigned char *A, int N, int K, int R) {
	for(int i = 0; i < R; i++){
		getK2[i] = A[i];
	}
	for(int i = 0; i < K; i++){
		col2[i] = i;
	}
  	
  	for(int i = 0; i < N; i++){
  		if(i < K) inScaf2[i] = 1;
  		else inScaf2[i] = 0;
  	}
  	
  	for(int i = 0; i < K; i++){
  		unq2.push(i-K+K);
  	}

  
  	for(int i = 0; i < N; i++){
  		col2[i+K] = GetRequest();
  		if(inScaf2[col2[i+K]]) continue; //do nothing
  		inScaf2[col2[i+K]] = 1;
  		while(true){
  			int a = unq2.front();
  			unq2.pop();
  			if(getK2[a]){
  				PutBack(col2[a]);
  				inScaf2[col2[a]] = 0;
  				break;
  			}
  		}
  		unq2.push(i+K);
  	}

}

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