Submission #1015618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015618		parsadox2	Last supper (IOI12_supper)	C++17	100 / 100	95 ms	14532 KiB

advisor

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

#define F first
#define S second

using namespace std;

const int N = 1e5 + 10;

int n , m , k , ar[N] , las[N];
vector <int> pos[N];
bool B[N << 1];

void ComputeAdvice(int *C, int nn, int kk, int mm){
	n = nn;
	m = mm;
	k = kk;
	for(int i = 0 ; i < n ; i++)
	{
		ar[i] = C[i];
		pos[i].push_back(n + 1);
	}
	for(int i = n - 1 ; i >= 0 ; i--)
		pos[ar[i]].push_back(i);
	set <pair <int , int>> st;
	for(int i = 0 ; i < k ; i++)
	{
		las[i] = i;
		st.insert(make_pair(pos[i].back() , i));
	}
	for(int i = 0 ; i < n ; i++)
	{
		int x = ar[i];
		auto it = st.find(make_pair(i , x));
		if(it != st.end())
		{
			st.erase(it);
			pos[x].pop_back();
			las[x] = i + k;
			st.insert(make_pair(pos[x].back() , x));
		}
		else
		{
			auto rem = st.end();  rem--;
			auto now = *rem;
			B[las[now.S]] = 1;
			//cout << now.S << " " << x << endl;
			st.erase(rem);
			pos[x].pop_back();
			las[x] = i + k;
			st.insert(make_pair(pos[x].back() , x));
		}
	}
	for(int i = 0 ; i < n + k ; i++)
	{
		//cout << B[i];
		WriteAdvice(B[i]);
	}
	//cout << endl;
}

assistant

#include <bits/stdc++.h>
#include "assistant.h"
 
#define F first
#define S second

using namespace std;

const int N = 1e5 + 10;

int n2 , k2 , r2;

void Assist(unsigned char *ar, int nn, int kk, int rr) {
	n2 = nn;
	k2 = kk;
	r2 = rr;
	set <int> st;
	for(int i = 0 ; i < k2 ; i++)
		st.insert(i);
	vector <int> vec;
	for(int i = 0 ; i < k2 ; i++)  if(ar[i])
		vec.push_back(i);
	for(int i = k2 ; i < k2 + n2 ; i++)
	{
		int now = GetRequest();
		if(st.find(now) == st.end())
		{
			PutBack(vec.back());
			st.erase(vec.back());
			st.insert(now);
			vec.pop_back();
		}
		if(ar[i])
			vec.push_back(now);
	}
}

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