Submission #761148

#	Time	Username	Problem	Language	Result	Execution time	Memory
761148		NothingXD	Last supper (IOI12_supper)	C++17	43 / 100	244 ms	16856 KiB

advisor

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

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename H, typename... T>
void debug_out(H h, T... t){
	cerr << h << ' ';
	debug_out(t...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;

int n, lg, f[maxn];
bool mark[maxn];
vector<int> idx[maxn];
set<pii> q;
void add(int idx, int x){
	for (; idx <= n; idx += idx & -idx) f[idx] += x;
}

int get(int idx){
	int res = 0;
	for (; idx; idx -= idx & -idx) res += f[idx];
	return res;
}

void give(int x){
	for (int i = lg-1; ~i; i--){
		WriteAdvice((x >> i)&1);
	}
}

void ComputeAdvice(int *C, int N, int K, int M) {
	n = N;
	for (int i = 0; i < n; i++){
		idx[i].push_back(n);
	}
	for (int i = n-1; ~i; i--){
		idx[C[i]].push_back(i);
	}
	for (int i = 0; i < K; i++){
		q.insert({idx[i].back(), i});
		mark[i] = true;
		add(i+1, 1);
	}
	lg = 32 - __builtin_clz(K);
	for (int i = 0; i < n; i++){
		if (mark[C[i]]){
			q.erase({idx[C[i]].back(), C[i]});
			idx[C[i]].pop_back();
			q.insert({idx[C[i]].back(), C[i]});
			continue;
		}
		auto it = q.end();
		it--;
		pii tmp = *it;
		q.erase(it);
		idx[C[i]].pop_back();
		q.insert({idx[C[i]].back(), C[i]});
		give(get(tmp.S));
		add(tmp.S+1, -1);
		mark[tmp.S] = false;
		add(C[i]+1, 1);
		mark[C[i]] = true;
	}
}

assistant

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

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

/*void debug_out(){cerr << endl;}

template<typename H, typename... T>
void debug_out(H h, T... t){
	cerr << h << ' ';
	debug_out(t...);
}*/

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;

int nn, F[maxn];
bool Mark[maxn];

void Add(int idx, int x){
	for (; idx <= nn; idx += idx & -idx) F[idx] += x;
}

int Find(int idx){
	int res = 0;
	for (int i = 19; ~i; i--){
		int tmp = res + (1 << i);
		if (tmp <= nn && F[tmp] < idx){
			idx -= F[tmp];
			res = tmp;
		}
	}
	return res;
}

void Assist(unsigned char *A, int N, int K, int R) {
	nn = N;
	int lg = 32 - __builtin_clz(K);
	for (int i = 0; i < K; i++){
		Mark[i] = true;
		Add(i+1, 1);
	}
	int ptr = 0;
	for (int i = 0; i < nn; i++){
		int tmp = GetRequest();
		if (Mark[tmp]) continue;
		int x = 0;
		for (int j = ptr; j < ptr + lg; j++){
			x += (A[j] << (ptr + lg - j - 1));
		}
		ptr += lg;
		int idx = Find(x+1);
		PutBack(idx);
		Add(idx+1, -1);
		Mark[idx] = false;
		Mark[tmp] = true;
		Add(tmp+1, 1);
	}
}

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