Submission #653295

#	Time	Username	Problem	Language	Result	Execution time	Memory
653295		ymm	Last supper (IOI12_supper)	C++17	100 / 100	114 ms	13004 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100000;
int ans[N], ans_pos[N], ans_ptr;
int cnt[N];
vector<int> pos[N];

void ComputeAdvice(int *c, int n, int k, int m)
{
	LoopR (i,0,n)
		pos[c[i]].push_back(i);
	set<pii,greater<pii>> pq;
	Loop (i,0,k) {
		pq.insert({pos[i].size()? pos[i].back(): n, i});
		cnt[i] = 1;
		ans_pos[i] = ans_ptr++;
	}
	Loop (i,0,n) {
		if (cnt[c[i]]) {
			pq.erase({pos[c[i]].size()? pos[c[i]].back(): n, c[i]});
			cnt[c[i]]++;
			pos[c[i]].pop_back();
			pq.insert({pos[c[i]].size()? pos[c[i]].back(): n, c[i]});
			continue;
		}
		auto [_, x] = *pq.begin();
		//cerr << "c[" << i << "] = " << c[i] << " removes " << x << '\n';
		ans[ans_pos[x]] = cnt[x];
		//cerr << "ans[" << ans_pos[x] << "] = " << cnt[x] << '\n';
		cnt[x] = 0;
		pq.erase(pq.begin());
		pos[c[i]].pop_back();
		pq.insert({pos[c[i]].size()? pos[c[i]].back(): n, c[i]});
		cnt[c[i]] = 1;
		ans_pos[c[i]] = ans_ptr++;
	}
	Loop (i,0,n) {
		if (cnt[i]) {
			ans[ans_pos[i]] = cnt[i];
			//cerr << "ans[" << ans_pos[i] << "] = " << cnt[i] << '\n';
			cnt[i] = 0;
		}
	}
	Loop (i,0,ans_ptr)
		Loop (j,0,ans[i])
			WriteAdvice(i&1);
}

assistant

#include "assistant.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100000;
int lck[N];
vector<int> zero_lck;
int n, k, r;

unsigned char *a;
int ap;
int get_bs()
{
	int x = a[ap];
	int tmp = ap;
	while (ap < r && a[ap] == x)
		++ap;
	return ap - tmp;
}

void Assist(unsigned char *_a, int _n, int _k, int _r)
{
	a = _a;
	n = _n; k = _k; r = _r;
	assert(n+k == r);
	Loop (i,0,k) {
		if (!(lck[i] = get_bs() - 1))
			zero_lck.push_back(i);
		//cerr << "lck[" << i << "] = " << lck[i] << '\n';
	}
	Loop (i,0,n) {
		int x = GetRequest();
		if (lck[x]) {
			if (!--lck[x])
				zero_lck.push_back(x);
			//cerr << "lck[" << x << "] = " << lck[x] << '\n';
		} else {
			int y = zero_lck.back();
			zero_lck.pop_back();
			//cerr << "PutBack(" << y << ")\n";
			PutBack(y);
			if (!(lck[x] = get_bs() - 1))
				zero_lck.push_back(x);
			//cerr << "lck[" << x << "] = " << lck[x] << '\n';
		}
	}
}

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