oj.uz

Submission #65205

# Submission time Handle Problem Language Result Execution time Memory
65205 2018-08-07T04:24:33 Z gnoor Last supper (IOI12_supper) C++17
100 / 100
 213 ms 12000 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;
			ins[C[i]]=true;
			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(req);
			rminscf.erase(req);
		}
		
		if (A[i+K]) inscf.insert(req);
		else rminscf.insert(req);
	}

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 752 KB Output is correct
2 Correct 5 ms 1048 KB Output is correct
3 Correct 7 ms 1496 KB Output is correct
4 Correct 8 ms 1560 KB Output is correct
5 Correct 11 ms 1644 KB Output is correct
6 Correct 11 ms 1968 KB Output is correct
7 Correct 10 ms 2008 KB Output is correct
8 Correct 11 ms 2008 KB Output is correct
9 Correct 11 ms 2008 KB Output is correct
10 Correct 12 ms 2232 KB Output is correct
11 Correct 13 ms 2232 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2576 KB Output is correct
2 Correct 79 ms 6152 KB Output is correct
3 Correct 170 ms 11064 KB Output is correct
4 Correct 95 ms 11064 KB Output is correct
5 Correct 103 ms 11064 KB Output is correct
6 Correct 135 ms 11064 KB Output is correct
7 Correct 182 ms 11408 KB Output is correct
8 Correct 134 ms 11408 KB Output is correct
9 Correct 98 ms 11408 KB Output is correct
10 Correct 203 ms 11664 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 11664 KB Output is correct
2 Correct 175 ms 11664 KB Output is correct
3 Correct 207 ms 11664 KB Output is correct
4 Correct 175 ms 11672 KB Output is correct
5 Correct 176 ms 11672 KB Output is correct
6 Correct 177 ms 11672 KB Output is correct
7 Correct 182 ms 11672 KB Output is correct
8 Correct 150 ms 11672 KB Output is correct
9 Correct 180 ms 11672 KB Output is correct
10 Correct 197 ms 11672 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11672 KB Output is correct
2 Correct 11 ms 11672 KB Output is correct
3 Correct 8 ms 11672 KB Output is correct
4 Correct 9 ms 11672 KB Output is correct
5 Correct 10 ms 11672 KB Output is correct
6 Correct 13 ms 11672 KB Output is correct
7 Correct 10 ms 11672 KB Output is correct
8 Correct 13 ms 11672 KB Output is correct
9 Correct 14 ms 11672 KB Output is correct
10 Correct 14 ms 11672 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 11744 KB Output is correct - 120000 bits used
2 Correct 207 ms 11744 KB Output is correct - 122000 bits used
3 Correct 169 ms 11744 KB Output is correct - 125000 bits used
4 Correct 171 ms 11744 KB Output is correct - 125000 bits used
5 Correct 191 ms 11744 KB Output is correct - 125000 bits used
6 Correct 180 ms 11752 KB Output is correct - 125000 bits used
7 Correct 213 ms 11752 KB Output is correct - 124828 bits used
8 Correct 167 ms 11752 KB Output is correct - 124910 bits used
9 Correct 201 ms 12000 KB Output is correct - 125000 bits used
10 Correct 157 ms 12000 KB Output is correct - 125000 bits used