Submission #1308720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308720		Jawad_Akbar_JJ	최후의 만찬 (IOI12_supper)	C++20	100 / 100	108 ms	8348 KiB

advisor

#include <iostream>
#include <set>

#include "advisor.h"
#include "assistant.h"

using namespace std;
const int Nn = 1<<18;
int a[Nn], ind1[Nn], ind2[Nn], prv[Nn], nxt[Nn], pres[Nn], used[Nn];

void ComputeAdvice(int *C, int n, int k, int m){
	for (int i=1;i<=k;i++)
		a[i] = i-1;
	for (int i=k+1;i<=k+n;i++)
		a[i] = C[i - k - 1];

	for (int i=1;i<=n+k;i++)
		prv[i] = ind1[a[i]], ind1[a[i]] = i;

	for (int i=n+k;i>=1;i--){
		if (ind2[a[i]])
			nxt[i] = ind2[a[i]];
		else
			nxt[i] = 1e6;
		ind2[a[i]] = i;
	}

	set<pair<int, int>> st;
	for (int i=1;i<=k;i++)
		st.insert({nxt[i], i-1}), pres[i-1] = 1;

	for (int i=k+1;i<=n+k;i++){
		if (pres[a[i]]){
			st.erase({prv[i], a[i]});
			st.insert({nxt[i], a[i]});
			used[prv[i]] = 1;
		}
		else{
			auto [mx, id] = *rbegin(st);
			st.erase({mx, id});
			pres[id] = 0;
			st.insert({nxt[i], a[i]}), pres[a[i]] = 1;
		}
	}

	for (int i=1;i<=n+n;i++)
		WriteAdvice(used[i]);
}

assistant

#include <iostream>
#include <set>

#include "advisor.h"
#include "assistant.h"

using namespace std;

void Assist(unsigned char *A, int n, int k, int R){
	set<int> O, Z;
	for (int i=0;i<k;i++){
		if ((int)A[i] == 0)
			Z.insert(i);
		else
			O.insert(i);
	}

	for (int i=0;i<n;i++){
		int nw = GetRequest();
		if (O.find(nw) == O.end()){
			PutBack(*Z.begin());
			Z.erase(Z.begin());

			O.insert(nw);
		}
		if ((int)A[i+k] == 0)
			O.erase(nw), Z.insert(nw);
	}
}

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