Submission #146412

#	Time	Username	Problem	Language	Result	Execution time	Memory
146412		Sorting	Last supper (IOI12_supper)	C++14	0 / 100	143 ms	18928 KiB

advisor

#include <bits/stdc++.h>
#include "advisor.h"

using namespace std;

const int MAXN = 1e5 + 7;

int nxt[MAXN];

struct cmp{
	bool operator()(int lvalue, int rvalue){
		return nxt[lvalue] > nxt[rvalue];
	}
};

set<int, cmp> pq;
int log_k, cnt[MAXN];
vector<int> v[MAXN];

int pos[MAXN];
vector<bool> ans;

void ComputeAdvice(int *C, int N, int K, int M) {
	for(int i = 0; i < N; ++i){
		v[C[i]].push_back(i);
	}
	for(int i = 0; i < N; ++i){
		v[i].push_back(N);
		nxt[i] = v[i][0];
		cnt[i] = 0;
	}

	for(int i = 0; i < N + K; ++i){
		ans.push_back(false);
	}

	for(int i = 0; i < K; ++i){
		pos[i] = i;
		pq.insert(i);
	}

	for(int i = 0; i < N; ++i){
		if(pq.find(C[i]) == pq.end()){
			int x = *pq.begin();
			ans[pos[x]] = false;

			pq.erase(x);
			nxt[x] = v[x][++cnt[x]];
			nxt[C[i]] = v[C[i]][++cnt[C[i]]];
			pq.insert(C[i]); 

			pos[C[i]] = K + i;
		}
		else{
			ans[pos[C[i]]] = true;

			pq.erase(C[i]);
			nxt[C[i]] = v[C[i]][++cnt[C[i]]];
			pq.insert(C[i]);

			pos[C[i]] = K + i;
		}
	}

	for(bool b: ans){
		WriteAdvice(b);
	}
}

assistant

#include <bits/stdc++.h>
#include "assistant.h"

using namespace std;

const int MAXN = 1e5 + 7;

vector<int> v2;
bool b[MAXN], ok[MAXN];

void Assist(unsigned char *A, int N, int K, int R) {
	for(int i = 0; i < K; ++i){
		if(!A[i]){
			ok[i] = true;
			v2.push_back(i);
		}
		b[i] = true;
	}

	for(int i = 0; i < N; ++i){
		int x = GetRequest();
		if(b[x]){
			ok[x] = !A[i + K];
			v2.push_back(x);
			continue;
		}

		while(true){
			if(b[v2.back()] && ok[v2.back()]){
				b[v2.back()] = false;
				ok[v2.back()] = false;
				PutBack(v2.back());
				ok[x] = !A[i + K];
				b[x] = true;
				v2.push_back(x);
				break;
			}
			v2.pop_back();
		}
	}
}
/*
4 2 100
2 0 3 2
*/
/*
g++ -DEVAL -Wall -static -std=c++11 -O2 -o supper grader.cpp assistant.cpp advisor.cpp
*/

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