제출 #577263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
577263		Justin1	최후의 만찬 (IOI12_supper)	C++14	34 / 100	471 ms	84868 KiB

advisor

#include <bits/stdc++.h>
#define f first
#define s second
#include "advisor.h"
using namespace std;

string dectobin(int x, int mx) {
	string res = "";
	for (int i = mx; i >= 0; i--) {
		if ((1 << i) & x) res += '1';
		else res += '0';
	}
	return res;
}

int seg[400005];

int qry(int t1, int t2, int id, int l, int r) {
	if (r < t1 || t2 < l) return 0;
	if (t1 <= l && r <= t2) return seg[id];
	int mid = (l+r)/2;
	return qry(t1,t2,id*2,l,mid)+qry(t1,t2,id*2+1,mid+1,r);
}

void upd(int tar, int val, int id, int l, int r) {
	if (l == r) {
		seg[id] = val;
		return;
	}
	int mid = (l+r)/2;
	if (tar <= mid) upd(tar,val,id*2,l,mid);
	else upd(tar,val,id*2+1,mid+1,r);
	seg[id] = seg[id*2] + seg[id*2+1];
}

void ComputeAdvice(int *C, int N, int K, int M) {
	int mx = log2(K-1);
	for (int i = 0; i < K; i++) upd(i,1,1,0,N-1);
	deque<int> pos[100005];
	for (int i = 0; i < N; i++) pos[C[i]].push_back(i);
	for (int i = 0; i < N; i++) pos[i].push_back(1e9);
	set<pair<int,int>> cur;
	for (int i = 0; i < K; i++) cur.insert({pos[i][0],i});
	for (int i = 0; i < N; i++) {
		string tmp;
		if (cur.find({pos[C[i]][0],C[i]}) != cur.end()) {
			cur.erase({pos[C[i]][0],C[i]});
			pos[C[i]].pop_front();
			cur.insert({pos[C[i]][0],C[i]});
			tmp = dectobin(0,mx);
		} else {
			pos[C[i]].pop_front();
			int tar = (*cur.rbegin()).s;
			upd(tar,0,1,0,N-1);
			tmp = dectobin(qry(0,tar,1,0,N-1),mx);
			upd(C[i],1,1,0,N-1);
			cur.erase(*cur.rbegin());
			cur.insert({pos[C[i]][0],C[i]});
		}
		for (auto j : tmp) WriteAdvice(j-'0');
	}
}

assistant

#include <bits/stdc++.h>
#define f first
#define s second
#include "assistant.h"
using namespace std;

int res[100005];
int used[100005];
int segtree[400005];

int binsearch(int tar, int id, int l, int r) {
	if (l == r) return l;
	int mid = (l+r)/2;
	if (tar < segtree[id*2]) return binsearch(tar,id*2,l,mid);
	else return binsearch(tar-segtree[id*2],id*2+1,mid+1,r);
}

void update(int tar, int val, int id, int l, int r) {
	if (l == r) {
		segtree[id] = val;
		return;
	}
	int mid = (l+r)/2;
	if (tar <= mid) update(tar,val,id*2,l,mid);
	else update(tar,val,id*2+1,mid+1,r);
	segtree[id] = segtree[id*2] + segtree[id*2+1];
}

void Assist(unsigned char *A, int N, int K, int R) {
	int lg = log2(K-1)+1;
	for (int i = 0; i < R; i++) {
		res[i/lg] += (1 << (lg - i % lg - 1)) * A[i];
	}
	for (int i = 0; i < K; i++) {
		used[i] = 1;
		update(i,1,1,0,N-1);
	}
	for (int i = 0; i < N; i++) {
		int cur = GetRequest();
		if (used[cur]) continue;
		int tmp = binsearch(res[i],1,0,N-1);
		assert(used[tmp]);
		PutBack(tmp);
		used[tmp] = 0;
		used[cur] = 1;
		update(tmp,0,1,0,N-1);
		update(cur,1,1,0,N-1);
	}
}

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