oj.uz

Submission #295486

# Submission time Handle Problem Language Result Execution time Memory
295486 2020-09-09T17:17:02 Z rqi Last supper (IOI12_supper) C++14
0 / 100
 88 ms 8096 KB 
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;

#define mp make_pair
#define f first
#define s second

const int mx = 200005;

int col[mx];

int nex[mx]; //next needed
int curpos[mx]; //current position of a color

bool getK[mx]; //does this index get kicked off before needed again

bool inScaf[mx]; //is this color in the scaffold
queue<int> unq; //indices of C that have not been queried yet

void ComputeAdvice(int *C, int N, int K, int M) {

	// cout << "B1" << "\n";
	// cout.flush();
	for(int i = 0; i < N; i++){
		col[i+K] = C[i];
	}
	for(int i = 0; i < K; i++){
		col[i] = i;
	}


	for(int i = 0; i < N; i++){
		curpos[i] = N+K;
	}
	for(int i = N-1; i >= -K; i--){
		nex[i+K] = curpos[col[i+K]];
		curpos[col[i+K]] = i+K;
		//cout << i+K << " " << nex[i+K] << "\n";
	}
	// cout << "B2" << "\n";
	// cout.flush();
	priority_queue<pi> pq; //when needed again, index+K
	for(int i = 0; i < K; i++){
		pq.push(mp(nex[i-K+K], i-K+K));
		inScaf[i] = 1;
	}
	for(int i = 0; i < N; i++){
		if(inScaf[col[i+K]]) continue;
		pi a = pq.top();
		//cout << i << " " << a.f << " " << a.s << "\n";
		pq.pop();
		getK[a.s] = 1; //got kicked off
		pq.push(mp(nex[i+K], i+K));
		//cout << col[i+K] << " " << col[a.s] << "\n";
		inScaf[col[i+K]] = 1;
		inScaf[col[a.s]] = 0;
	}
	// cout << "B3" << "\n";
	// cout.flush();
	for(int i = -K; i < N; i++){
		WriteAdvice(getK[i+K]);
		//cout << i+K << " " << col[i+K] << " " << nex[i+K] << " " << getK[i+K] << "\n";
	}

	for(int i = 0; i < N; i++){
		if(i < K) inScaf[i] = 1;
		else inScaf[i] = 0;
	}
	for(int i = 0; i < K; i++){
		unq.push(i-K+K);
	}
	
	// cout << "B4" << "\n";
	// cout.flush();
	for(int i = 0; i < N; i++){
		if(inScaf[col[i+K]]) continue; //do nothing
		inScaf[col[i+K]] = 1;
		while(true){
			int a = unq.front();
			unq.pop();
			if(getK[a]){
				inScaf[col[a]] = 0;
				break;
			}
		}
		unq.push(i+K);
	}

	// cout << "B5" << "\n";
	// cout.flush();
}

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;

const int mx = 200005;

int col2[mx];
bool getK2[mx]; //does this index get kicked off before needed again

bool inScaf2[mx]; //is this col2or in the scaffold
queue<int> unq2; //indices of C that have not been queried yet

void Assist(unsigned char *A, int N, int K, int R) {
	for(int i = 0; i < R; i++){
		getK2[i] = A[i];
	}
	for(int i = 0; i < K; i++){
		col2[i] = i;
	}
  	
  	for(int i = 0; i < N; i++){
  		if(i < K) inScaf2[i] = 1;
  		else inScaf2[i] = 0;
  	}
  	
  	for(int i = 0; i < K; i++){
  		unq2.push(i-K+K);
  	}

  
  	for(int i = 0; i < N; i++){
  		col2[i+K] = GetRequest();
  		if(inScaf2[col2[i+K]]) continue; //do nothing
  		inScaf2[col2[i+K]] = 1;
  		while(true){
  			int a = unq2.front();
  			unq2.pop();
  			if(getK2[a]){
  				PutBack(col2[a]);
  				inScaf2[col2[a]] = 0;
  				break;
  			}
  		}
  		unq2.push(i+K);
  	}

}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1020 KB Output is correct
2 Runtime error 1 ms 640 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1536 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 6584 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1424 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 7848 KB Output isn't correct - not an optimal way
2 Incorrect 88 ms 8080 KB Output isn't correct - not an optimal way
3 Incorrect 82 ms 8024 KB Output isn't correct - not an optimal way
4 Incorrect 88 ms 8032 KB Output isn't correct - not an optimal way
5 Incorrect 83 ms 8032 KB Output isn't correct - not an optimal way
6 Incorrect 84 ms 8032 KB Output isn't correct - not an optimal way
7 Incorrect 81 ms 8032 KB Output isn't correct - not an optimal way
8 Incorrect 81 ms 8096 KB Output isn't correct - not an optimal way
9 Incorrect 81 ms 8032 KB Output isn't correct - not an optimal way
10 Correct 81 ms 8032 KB Output is correct - 125000 bits used