Submission #146471

#	Time	Username	Problem	Language	Result	Execution time	Memory
146471		Sorting	Last supper (IOI12_supper)	C++14	100 / 100	187 ms	21232 KiB

advisor

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

using namespace std;

const int MAXN = 1e5 + 7;

int nxt[MAXN];

struct cmp{
	bool operator()(pair<int, int> lvalue, pair<int, int> rvalue){
		if(lvalue.second != rvalue.second){
			return lvalue.second > rvalue.second;
		}

		return lvalue.first > rvalue.first;
	}
};

set<pair<int, int>, cmp> pq;
int 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, nxt[i]});
	}

	for(int i = 0; i < N; ++i){
		if(pq.find({C[i], nxt[C[i]]}) == pq.end()){
			pair<int, int> p = *pq.begin();
			int x = p.first;

			ans[pos[x]] = false;

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

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

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

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

	while(!pq.empty()){
		pair<int, int> p = *pq.begin();
		int x = p.first;

		ans[pos[x]] = true;

		pq.erase(p);
	}

	for(bool b: ans){
		WriteAdvice(b);
		//cout << b << " ";
	}
	//cout << endl;
}

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: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 35 / 35
• Subtask 5: 39 / 39