제출 #288210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288210		emanIaicepsa	최후의 만찬 (IOI12_supper)	C++14	43 / 100	334 ms	13000 KiB

advisor

#include "advisor.h"
#include<bits/stdc++.h>
#define pb emplace_back
#define pii pair<ll,ll>
#define all(n) (n).begin(),(n).end()
#define ll long long
using namespace std;

int pos[100005], bk[100005], in[100005];
int bit1[100005];

void add1(int x,int v,int N){
	x++;
	for(;x<=N;x+=x&-x) bit1[x]+=v;
}

int query(int x){
	x++;
	int ans = 0;
	for(;x;x-=x&-x) ans += bit1[x];
	return ans;
}

void Write(int x,int K){
	int mx = __lg(K);
	vector<int> v;
	for(int i=0;i<=mx;i++){
		v.pb(x&1);
		x>>=1;
	}
	reverse(all(v));
	for(auto &i:v){
		WriteAdvice(i);
	}
}

void ComputeAdvice(int *C, int N, int K, int M) {
	for(int i=0;i<N;i++){
		pos[i] = N+1;
	}
	for(int i=N-1;i>=0;i--){
		bk[i] = pos[C[i]];
		pos[C[i]] = i;
	}
	priority_queue<pii> pq;
	for(int i=0;i<K;i++){
		in[i] = 1;
		add1(i, 1, N);
		pq.push({pos[i],i});
	}
	for(int i=0;i<N;i++){
		if(in[C[i]]){
			pq.push({bk[i], C[i]});
		}
		else{
			int x = pq.top().second; pq.pop();
			pq.push({bk[i], C[i]});
			in[C[i]] = 1, in[x] = 0;
			Write(query(x),K);
			add1(C[i], 1, N); add1(x, -1, N);
		}
	}
}

assistant

#include<bits/stdc++.h>
#include "assistant.h"
using namespace std;
int in2[100005], bit2[100005];

void add2(int x,int val,int N){
	x++;
	for(;x<=N;x+=x&-x) bit2[x] += val;
}

int kth(int k,int N){
	int p = 0;
	for(int i=__lg(N);i>=0;i--){
		int np = p + (1<<i);
		if(np <= N && bit2[np] < k){
			p = np;
			k -= bit2[np];
		}
	}
	return p;
}

void Assist(unsigned char *A, int N, int K, int R) {
	int id = 0;
	for(int i=0;i<K;i++) in2[i] = 1, add2(i, 1, N);
	for(int i=0;i<N;i++){
		int x = GetRequest();
		if(in2[x]) continue;
		
		int rm = 0;
		for(int j=id;id<=j+__lg(K);id++){
			rm = rm * 2 + A[id];
		}
		rm = kth(rm, N);
		PutBack(rm);
		in2[rm] = 0;
		in2[x] = 1;
		add2(rm, -1, N);
		add2(x, 1, N);
	}
	assert(id <= R);
}

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