oj.uz

Submission #65204

# Submission time Handle Problem Language Result Execution time Memory
65204 2018-08-07T04:09:10 Z gnoor Last supper (IOI12_supper) C++17
0 / 100
 82 ms 6396 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 {
			while (!q.empty()&&!ins[q.top().second]) q.pop();
			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>
#include <cstdio>

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(req);
		else rminscf.insert(req);
	}

}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 4916 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 4916 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 Runtime error 53 ms 5880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 60 ms 6096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 59 ms 6204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 60 ms 6324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 82 ms 6324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 58 ms 6396 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 57 ms 6396 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 56 ms 6396 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 58 ms 6396 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 72 ms 6396 KB Execution killed with signal 11 (could be triggered by violating memory limits)