제출 #295545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295545		rqi	최후의 만찬 (IOI12_supper)	C++14	100 / 100	137 ms	11504 KiB

advisor

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

typedef pair<int, int> pi;

#define ins insert
#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

void ComputeAdvice(int *C, int N, int K, int M) {
	//cout << N << " " << K << "\n";
	// cout << "B1" << "\n";
	// cout.flush();
	for(int i = 0; i < N; i++){
		col[i+K] = C[i];
		//cout << C[i] << " ";
	}
	//cout << "\n";
	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();
	set<pi> pq; //when needed again, index+K
	for(int i = 0; i < K; i++){
		pq.ins(mp(nex[i-K+K], i-K+K));
		inScaf[i] = 1;
	}
	for(int i = 0; i < N; i++){
		if(inScaf[col[i+K]]){
			pi a = *(pq.begin());
			assert(i+K == a.f);
			pq.erase(a);
			pq.ins(mp(nex[i+K], i+K));
			continue;
		}
		pi a = *(prev(pq.end()));
		//cout << i << " " << a.f << " " << a.s << "\n";
		pq.erase(a);
		getK[a.s] = 1; //got kicked off
		pq.ins(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";
	}

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

assistant

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

#define sz(x) (int)(x).size()
#define ins insert

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
set<int> unq2; //indices of C that have not been queried yet
int lastc[mx];

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.insert(i-K+K);
  	}

  	for(int i = 0; i < N; i++){
  		lastc[i] = -1;
  	}
  
  	for(int i = 0; i < N; i++){
  		//cout << "i: " << i << "\n";
  		col2[i+K] = GetRequest();
  		if(inScaf2[col2[i+K]]){
  			if(unq2.count(lastc[col2[i+K]])) unq2.erase(lastc[col2[i+K]]);
  			unq2.ins(i+K);
  			continue; //do nothing
  		}
  		inScaf2[col2[i+K]] = 1;
  		while(true){
  			int a = *(unq2.begin());
  			unq2.erase(a);
  			if(getK2[a]){
  				// cout << "a: " << a << " " << col2[a] << "\n";
  				// cout.flush();
  				PutBack(col2[a]);
  				inScaf2[col2[a]] = 0;
  				break;
  			}
  		}
  		unq2.insert(i+K);
  		lastc[col2[i+K]] = i+K;
  	}

}

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