oj.uz

Submission #288210

# Submission time Handle Problem Language Result Execution time Memory
288210 2020-09-01T10:09:20 Z emanIaicepsa Last supper (IOI12_supper) C++14
43 / 100
 334 ms 13000 KB 
#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);
		}
	}
}

#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1024 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct
3 Correct 2 ms 936 KB Output is correct
4 Correct 5 ms 1180 KB Output is correct
5 Correct 5 ms 1172 KB Output is correct
6 Correct 11 ms 1120 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 14 ms 1280 KB Output is correct
9 Correct 14 ms 1336 KB Output is correct
10 Correct 9 ms 1376 KB Output is correct
11 Correct 12 ms 1280 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1832 KB Output is correct
2 Correct 93 ms 5088 KB Output is correct
3 Correct 299 ms 11648 KB Output is correct
4 Correct 220 ms 9456 KB Output is correct
5 Correct 289 ms 11440 KB Output is correct
6 Correct 295 ms 11688 KB Output is correct
7 Correct 252 ms 10648 KB Output is correct
8 Correct 279 ms 10744 KB Output is correct
9 Correct 167 ms 8272 KB Output is correct
10 Correct 222 ms 10064 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 8552 KB Output is correct
2 Correct 235 ms 10368 KB Output is correct
3 Correct 237 ms 10304 KB Output is correct
4 Correct 212 ms 10200 KB Output is correct
5 Correct 169 ms 9696 KB Output is correct
6 Correct 237 ms 10560 KB Output is correct
7 Correct 224 ms 9976 KB Output is correct
8 Correct 334 ms 12720 KB Output is correct
9 Correct 149 ms 9688 KB Output is correct
10 Correct 238 ms 10312 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1144 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 10520 KB Output is partially correct - 772365 bits used
2 Correct 239 ms 10472 KB Output is partially correct - 742095 bits used
3 Correct 237 ms 10312 KB Output is partially correct - 712470 bits used
4 Correct 236 ms 10304 KB Output is partially correct - 712005 bits used
5 Correct 231 ms 10304 KB Output is partially correct - 710610 bits used
6 Correct 235 ms 10344 KB Output is partially correct - 712155 bits used
7 Correct 236 ms 10304 KB Output is partially correct - 711090 bits used
8 Correct 236 ms 10336 KB Output is partially correct - 713340 bits used
9 Correct 237 ms 10312 KB Output is partially correct - 712830 bits used
10 Correct 332 ms 13000 KB Output is partially correct - 1117620 bits used