oj.uz

Submission #65202

# Submission time Handle Problem Language Result Execution time Memory
65202 2018-08-07T03:54:35 Z gnoor Last supper (IOI12_supper) C++17
0 / 100
 2500 ms 12528 KB 
#include "advisor.h"

#include <queue>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

int last[100100];
int nxt[100100];

priority_queue<pair<int,int>> q;

int ans[200100];
int posinq[100100];
bool ins[100100];

void ComputeAdvice(int *C, int N, int K, int M) {
	for (int i=0;i<N;i++) {
		last[i]=N;
	}

	for (int i=N-1;i>=0;i--) {
		nxt[i]=last[C[i]];
		last[C[i]]=i;
	}

	for (int i=0;i<K;i++) {
		q.push({last[i],i});
		posinq[i]=i;
		ins[i]=true;
	}
	for (int i=0;i<N;i++) {
		if (ins[C[i]]) {
			//is in s
			ans[posinq[C[i]]]=1;
			posinq[C[i]]=i+K;
			q.push({nxt[i],C[i]});
		} else {
			ans[posinq[q.top().second]]=0;
			ins[q.top().second]=false;
			q.pop();

			posinq[C[i]]=i+K;
			q.push({nxt[i],C[i]});
		}
	}
	for (int i=0;i<N+K;i++) WriteAdvice(ans[i]);
}

#include "assistant.h"

#include <vector>
#include <set>

using namespace std;

int cnt[100100];
bool removable[100100];

set<int> rminscf;
set<int> inscf;

void Assist(unsigned char *A, int N, int K, int R) {

	for (int i=0;i<K;i++) {
		if (A[i]) inscf.insert(i);
		else rminscf.insert(i);
	}

	int req;
	for (int i=0;i<N;i++) {
		req=GetRequest();
		if (inscf.find(req)==inscf.end()&&rminscf.find(req)==rminscf.end()) {
			//req is not in scf
			PutBack(*rminscf.begin());
			rminscf.erase(rminscf.begin());
		} else {
			inscf.erase(inscf.find(req));
			rminscf.erase(rminscf.find(req));
		}
		
		if (A[i+K]) inscf.insert(i);
		else rminscf.insert(i);
	}

}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 6752 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 Runtime error 12 ms 6752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 141 ms 8608 KB Error - Putting back a color that is not on the scaffold
2 Incorrect 111 ms 8752 KB Error - Putting back a color that is not on the scaffold
3 Runtime error 116 ms 9676 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 133 ms 12520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 127 ms 12528 KB Error - Putting back a color that is not on the scaffold
6 Incorrect 123 ms 12528 KB Error - Putting back a color that is not on the scaffold
7 Runtime error 120 ms 12528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 108 ms 12528 KB Error - Putting back a color that is not on the scaffold
9 Runtime error 130 ms 12528 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 105 ms 12528 KB Execution killed with signal 11 (could be triggered by violating memory limits)