oj.uz

Submission #49011

# Submission time Handle Problem Language Result Execution time Memory
49011 2018-05-21T06:50:36 Z Namnamseo Last supper (IOI12_supper) C++17
0 / 100
 453 ms 36072 KB 
#include "advisor.h"

#include <algorithm>
#include <set>
#include <vector>
#include <functional>

using namespace std;
typedef pair<int,int> pp;

#define pb push_back
#define all(z) z.begin(), z.end()

vector<int> occ[100001];
vector<bool> pd[100001];
int ind[100001];

void init(int *C, int n, int k){
	// clear
	for(int i=0; i<n; ++i){
		occ[i].clear();
		pd[i].clear();
		ind[i] = 0;
	}

	// init
	for(int i=0; i<k; ++i){
		occ[i].pb(-1);
		pd [i].pb(false);
		ind[i] = 1;
	}

	// occurence
	for(int i=0; i<n; ++i){
		int t=C[i];
		occ[t].pb(i);
		pd [t].pb(false);
	}

	// virtual last
	for(int i=0; i<n; ++i){
		occ[i].pb(n+1);
		pd [i].pb(false);
	}
}

void ComputeAdvice(int *C, int n, int k, int m) {
	init(C, n, k);

	int up_when[100010];
	int pull_what[100010];

	set<int> big;
	set<pp> big_next;
	
	for(int i=0; i<n; ++i) up_when[i] = -1;

	for(int i=0; i<k; ++i){
		big_next.insert({occ[i][ind[i]],i});
		big     .insert(i);
		up_when [i] = 0;
	}

	for(int i=0; i<n; ++i){
		int t=C[i];
		++ind[t];
		
		if(big.find(t) == big.end()){
			int down=(--big_next.end())->second;
			pull_what[i] = down;
			big_next.erase(--big_next.end());
			big.erase(down);

			pd[down][up_when[down]]=true;

			up_when[t]=ind[t]-1;
			big_next.insert({occ[t][ind[t]], t});
			big.insert(t);
		} else {
			big_next.erase({occ[t][ind[t]-1],t});
			big_next.insert({occ[t][ind[t]],t});
		}
	}

	// initial report.
	for(int i=0; i<k; ++i){
		WriteAdvice(pd[i][0]);
	}

	big.clear();
	for(int i=0; i<n; ++i) ind[i]=(i<k);
	for(int i=0; i<k; ++i) big.insert(i), up_when[i]=0;

	for(int i=0; i<n; ++i){
		int t=C[i];
		++ind[t];
		if(big.find(t) == big.end()){
			int d=pull_what[i];
			big.erase(d); big.insert(t);
			WriteAdvice(pd[t][ind[t]-1]);
		}
	}
}

#include "assistant.h"
#include <set>
using namespace std;

unsigned char *pt;
bool poll(){
	int ret=*pt;
	++pt;
	return ret;
}

#include <cstdio>
#include <queue>

int readInt(int len){
	int ret=0;
	for(;len--;){
		ret=(ret*2+poll());
	}
	return ret;
}

void Assist(unsigned char *a, int n, int k, int R) {
	pt=a;

	int len;
	for(len=0; (1<<len)<k; ++len);
	for(int i=0; i<n; i++){
		GetRequest();
		int t=readInt(len);
		if(t<k)
		PutBack(t);
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 13040 KB Error - Putting back a color that is not on the scaffold
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 15568 KB Error - Putting back a color when it is already on the scaffold
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 280 ms 31008 KB Error - Putting back a color that is not on the scaffold
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 31008 KB Error - Putting back a color when it is already on the scaffold
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 379 ms 34768 KB Error - Not putting back color when it is not on the scaffold
2 Incorrect 381 ms 35464 KB Error - Putting back a color that is not on the scaffold
3 Incorrect 379 ms 35920 KB Error - Putting back a color when it is already on the scaffold
4 Incorrect 388 ms 35976 KB Error - Putting back a color when it is already on the scaffold
5 Incorrect 329 ms 36040 KB Error - Putting back a color that is not on the scaffold
6 Incorrect 320 ms 36040 KB Error - Putting back a color that is not on the scaffold
7 Incorrect 351 ms 36040 KB Error - Putting back a color when it is already on the scaffold
8 Incorrect 346 ms 36040 KB Error - Putting back a color that is not on the scaffold
9 Incorrect 453 ms 36072 KB Error - Putting back a color when it is already on the scaffold
10 Incorrect 352 ms 36072 KB Error - Putting back a color that is not on the scaffold