Submission #49010

#	Time	Username	Problem	Language	Result	Execution time	Memory
49010		Namnamseo	최후의 만찬 (IOI12_supper)	C++17	0 / 100	2628 ms	371440 KiB

advisor

#include "advisor.h"

#include <algorithm>
#include <set>
#include <vector>
#include <functional>

using namespace std;
typedef pair<int,int> pp;

#define pb push_back
#define all(z) z.begin(), z.end()

vector<int> occ[100001];
vector<bool> pd[100001];
int ind[100001];

void init(int *C, int n, int k){
	// clear
	for(int i=0; i<n; ++i){
		occ[i].clear();
		pd[i].clear();
		ind[i] = 0;
	}

	// init
	for(int i=0; i<k; ++i){
		occ[i].pb(-1);
		pd [i].pb(false);
		ind[i] = 1;
	}

	// occurence
	for(int i=0; i<n; ++i){
		int t=C[i];
		occ[t].pb(i);
		pd [t].pb(false);
	}

	// virtual last
	for(int i=0; i<n; ++i){
		occ[i].pb(n+1);
		pd [i].pb(false);
	}
}

void ComputeAdvice(int *C, int n, int k, int m) {
	init(C, n, k);

	int up_when[100010];
	int pull_what[100010];

	set<int> big;
	set<pp> big_next;
	
	for(int i=0; i<n; ++i) up_when[i] = -1;

	for(int i=0; i<k; ++i){
		big_next.insert({occ[i][ind[i]],i});
		big     .insert(i);
		up_when [i] = 0;
	}

	for(int i=0; i<n; ++i){
		int t=C[i];
		++ind[t];
		printf("t %d\n",t);
		for(auto x:big_next){
			printf("%d nxt %d\n", x.second, x.first);
		}
		putchar(10);
		
		if(big.find(t) == big.end()){
			int down=(--big_next.end())->second;
			pull_what[i] = down;
			big_next.erase(--big_next.end());
			big.erase(down);

			printf("down %d: up_when %d\n", down, up_when[down]);
			pd[down][up_when[down]]=true;

			up_when[t]=ind[t]-1;
			big_next.insert({occ[t][ind[t]], t});
			big.insert(t);
		} else {
			big_next.erase({occ[t][ind[t]-1],t});
			big_next.insert({occ[t][ind[t]],t});
		}
	}

	// initial report.
	for(int i=0; i<k; ++i){
		WriteAdvice(pd[i][0]);
	}

	big.clear();
	for(int i=0; i<n; ++i) ind[i]=(i<k);
	for(int i=0; i<k; ++i) big.insert(i), up_when[i]=0;

	for(int i=0; i<n; ++i){
		int t=C[i];
		++ind[t];
		if(big.find(t) == big.end()){
			int d=pull_what[i];
			big.erase(d); big.insert(t);
			WriteAdvice(pd[t][ind[t]-1]);
		}
	}
}

assistant

#include "assistant.h"
#include <set>
using namespace std;

unsigned char *pt;
bool poll(){
	int ret=*pt;
	++pt;
	return ret;
}

#include <cstdio>
#include <queue>

int readInt(int len){
	int ret=0;
	for(;len--;){
		ret=(ret*2+poll());
	}
	return ret;
}

void Assist(unsigned char *a, int n, int k, int R) {
	pt=a;

	int len;
	for(len=0; (1<<len)<k; ++len);
	for(int i=0; i<n; i++){
		GetRequest();
		int t=readInt(len);
		if(t<k)
		PutBack(t);
	}
}

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