oj.uz

Submission #287996

# Submission time Handle Problem Language Result Execution time Memory
287996 2020-09-01T07:40:55 Z emanIaicepsa Last supper (IOI12_supper) C++17
40 / 100
 445 ms 16112 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];

void Write(int x,int N){
	int mx = __lg(N);
	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;
		pq.push({pos[i],i});
		//cout<<i<<" "<<pos[i]<<'\n';
	}
	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(x,N);
		}
	}
}

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

void Assist(unsigned char *A, int N, int K, int R) {
	int id = 0;
	for(int i=0;i<K;i++) in2[i] = 1;
	for(int i=0;i<N;i++){
		int x = GetRequest();
		if(in2[x]) continue;
		
		int rm = 0;
		for(int j=id;id<=j+__lg(N);id++){
			rm = rm * 2 + A[id];
		}
		//cout<<"RM : "<<rm<<'\n';
		PutBack(rm);
		in2[rm] = 0;
		in2[x] = 1;
	}
	assert(id <= R);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1020 KB Output is correct
2 Correct 2 ms 1012 KB Output is correct
3 Correct 1 ms 940 KB Output is correct
4 Correct 10 ms 1168 KB Output is correct
5 Correct 18 ms 1348 KB Output is correct
6 Correct 16 ms 1372 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 18 ms 1324 KB Output is correct
9 Correct 16 ms 1344 KB Output is correct
10 Correct 10 ms 1384 KB Output is correct
11 Correct 10 ms 1280 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2116 KB Output is correct
2 Correct 109 ms 5864 KB Output is correct
3 Correct 311 ms 12416 KB Output is correct
4 Correct 445 ms 16112 KB Output is correct
5 Correct 420 ms 15536 KB Output is correct
6 Correct 354 ms 13744 KB Output is correct
7 Correct 277 ms 11672 KB Output is correct
8 Correct 301 ms 11768 KB Output is correct
9 Correct 438 ms 15696 KB Output is correct
10 Correct 244 ms 10832 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 8552 KB Output is correct
2 Correct 260 ms 11392 KB Output is correct
3 Correct 257 ms 11600 KB Output is correct
4 Correct 237 ms 10928 KB Output is correct
5 Correct 191 ms 10200 KB Output is correct
6 Correct 262 ms 11336 KB Output is correct
7 Correct 250 ms 11000 KB Output is correct
8 Correct 374 ms 14000 KB Output is correct
9 Correct 159 ms 9944 KB Output is correct
10 Correct 262 ms 11248 KB Output is correct

Subtask #4
0 / 35.0

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

Subtask #5
14.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 10592 KB Output is partially correct - 875347 bits used
2 Correct 263 ms 10464 KB Output is partially correct - 841041 bits used
3 Correct 259 ms 10312 KB Output is partially correct - 807466 bits used
4 Correct 260 ms 10312 KB Output is partially correct - 806939 bits used
5 Correct 277 ms 10568 KB Output is partially correct - 805358 bits used
6 Correct 258 ms 10312 KB Output is partially correct - 807109 bits used
7 Correct 259 ms 10448 KB Output is partially correct - 805902 bits used
8 Correct 257 ms 10312 KB Output is partially correct - 808452 bits used
9 Correct 253 ms 10496 KB Output is partially correct - 807874 bits used
10 Correct 370 ms 13216 KB Output is partially correct - 1266636 bits used