oj.uz

Submission #295545

# Submission time Handle Problem Language Result Execution time Memory
295545 2020-09-09T18:22:08 Z rqi Last supper (IOI12_supper) C++14
100 / 100
 137 ms 11504 KB 
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;

#define ins insert
#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

void ComputeAdvice(int *C, int N, int K, int M) {
	//cout << N << " " << K << "\n";
	// cout << "B1" << "\n";
	// cout.flush();
	for(int i = 0; i < N; i++){
		col[i+K] = C[i];
		//cout << C[i] << " ";
	}
	//cout << "\n";
	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();
	set<pi> pq; //when needed again, index+K
	for(int i = 0; i < K; i++){
		pq.ins(mp(nex[i-K+K], i-K+K));
		inScaf[i] = 1;
	}
	for(int i = 0; i < N; i++){
		if(inScaf[col[i+K]]){
			pi a = *(pq.begin());
			assert(i+K == a.f);
			pq.erase(a);
			pq.ins(mp(nex[i+K], i+K));
			continue;
		}
		pi a = *(prev(pq.end()));
		//cout << i << " " << a.f << " " << a.s << "\n";
		pq.erase(a);
		getK[a.s] = 1; //got kicked off
		pq.ins(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";
	}

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

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

#define sz(x) (int)(x).size()
#define ins insert

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
set<int> unq2; //indices of C that have not been queried yet
int lastc[mx];

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.insert(i-K+K);
  	}

  	for(int i = 0; i < N; i++){
  		lastc[i] = -1;
  	}
  
  	for(int i = 0; i < N; i++){
  		//cout << "i: " << i << "\n";
  		col2[i+K] = GetRequest();
  		if(inScaf2[col2[i+K]]){
  			if(unq2.count(lastc[col2[i+K]])) unq2.erase(lastc[col2[i+K]]);
  			unq2.ins(i+K);
  			continue; //do nothing
  		}
  		inScaf2[col2[i+K]] = 1;
  		while(true){
  			int a = *(unq2.begin());
  			unq2.erase(a);
  			if(getK2[a]){
  				// cout << "a: " << a << " " << col2[a] << "\n";
  				// cout.flush();
  				PutBack(col2[a]);
  				inScaf2[col2[a]] = 0;
  				break;
  			}
  		}
  		unq2.insert(i+K);
  		lastc[col2[i+K]] = i+K;
  	}

}

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 1016 KB Output is correct
3 Correct 3 ms 940 KB Output is correct
4 Correct 3 ms 1212 KB Output is correct
5 Correct 5 ms 1104 KB Output is correct
6 Correct 5 ms 1168 KB Output is correct
7 Correct 7 ms 1232 KB Output is correct
8 Correct 5 ms 1248 KB Output is correct
9 Correct 5 ms 1232 KB Output is correct
10 Correct 8 ms 1704 KB Output is correct
11 Correct 7 ms 1240 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1728 KB Output is correct
2 Correct 56 ms 4620 KB Output is correct
3 Correct 124 ms 11504 KB Output is correct
4 Correct 82 ms 7160 KB Output is correct
5 Correct 91 ms 7152 KB Output is correct
6 Correct 106 ms 7920 KB Output is correct
7 Correct 122 ms 9456 KB Output is correct
8 Correct 98 ms 8944 KB Output is correct
9 Correct 80 ms 7152 KB Output is correct
10 Correct 132 ms 10744 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 7992 KB Output is correct
2 Correct 135 ms 10040 KB Output is correct
3 Correct 125 ms 10144 KB Output is correct
4 Correct 128 ms 9968 KB Output is correct
5 Correct 133 ms 9456 KB Output is correct
6 Correct 126 ms 10224 KB Output is correct
7 Correct 137 ms 9968 KB Output is correct
8 Correct 110 ms 9976 KB Output is correct
9 Correct 123 ms 9968 KB Output is correct
10 Correct 125 ms 9968 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1260 KB Output is correct
2 Correct 7 ms 1236 KB Output is correct
3 Correct 5 ms 1104 KB Output is correct
4 Correct 5 ms 1104 KB Output is correct
5 Correct 5 ms 1168 KB Output is correct
6 Correct 5 ms 1168 KB Output is correct
7 Correct 5 ms 1232 KB Output is correct
8 Correct 6 ms 1256 KB Output is correct
9 Correct 6 ms 1492 KB Output is correct
10 Correct 8 ms 1740 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 9456 KB Output is correct - 120000 bits used
2 Correct 123 ms 9712 KB Output is correct - 122000 bits used
3 Correct 125 ms 9968 KB Output is correct - 125000 bits used
4 Correct 129 ms 9976 KB Output is correct - 125000 bits used
5 Correct 128 ms 9968 KB Output is correct - 125000 bits used
6 Correct 126 ms 10224 KB Output is correct - 125000 bits used
7 Correct 125 ms 9968 KB Output is correct - 124828 bits used
8 Correct 125 ms 10224 KB Output is correct - 124910 bits used
9 Correct 125 ms 9968 KB Output is correct - 125000 bits used
10 Correct 113 ms 10224 KB Output is correct - 125000 bits used