oj.uz

Submission #49010

# Submission time Handle Problem Language Result Execution time Memory
49010 2018-05-21T06:50:03 Z Namnamseo Last supper (IOI12_supper) C++17
0 / 100
 2500 ms 371440 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];
		printf("t %d\n",t);
		for(auto x:big_next){
			printf("%d nxt %d\n", x.second, x.first);
		}
		putchar(10);
		
		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);

			printf("down %d: up_when %d\n", down, up_when[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 8 ms 13040 KB Error - Invalid Access
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2580 ms 185720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2556 ms 185720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 997 ms 371440 KB Error - Invalid Access
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2566 ms 185720 KB Time limit exceeded
2 Execution timed out 2628 ms 185720 KB Time limit exceeded
3 Execution timed out 2582 ms 185720 KB Time limit exceeded
4 Execution timed out 2579 ms 185720 KB Time limit exceeded
5 Execution timed out 2588 ms 185720 KB Time limit exceeded
6 Execution timed out 2585 ms 185720 KB Time limit exceeded
7 Execution timed out 2581 ms 185720 KB Time limit exceeded
8 Execution timed out 2581 ms 185720 KB Time limit exceeded
9 Execution timed out 2557 ms 185720 KB Time limit exceeded
10 Execution timed out 2536 ms 185720 KB Time limit exceeded