oj.uz

Submission #576432

# Submission time Handle Problem Language Result Execution time Memory
576432 2022-06-13T06:00:19 Z benson1029 Last supper (IOI12_supper) C++14
100 / 100
 161 ms 75440 KB 
#include "advisor.h"
#include<bits/stdc++.h>
using namespace std;

namespace advisor_var {
	deque<int> occ[100005];
	bool inset[100005];
	int id[100005];
	int cnt[200005];
	int timer = 0;
	multiset< pair<int,int> > st;
};

void ComputeAdvice(int *C, int N, int K, int M) {
	using namespace advisor_var;
	for(int i=0; i<N; i++) {
		occ[C[i]].push_back(i);
	}
	for(int i=0; i<N; i++) occ[i].push_back(1e9);
	for(int i=0; i<K; i++) {
		inset[i] = true;
		st.insert({occ[i].front(), i});
		id[i] = i;
	}
	timer = K;
	for(int i=0; i<N; i++) {
		if(inset[C[i]]) {
			++cnt[id[C[i]]];
			st.erase({occ[C[i]].front(), C[i]});
			occ[C[i]].pop_front();
			st.insert({occ[C[i]].front(), C[i]});
		} else {
			int curr = (*prev(st.end())).second;
			st.erase(prev(st.end()));
			inset[curr] = false;
			inset[C[i]] = true;
			occ[C[i]].pop_front();
			st.insert({occ[C[i]].front(), C[i]});
			id[C[i]] = timer;
			++timer;
		}
	}
	for(int i=0; i<timer; i++) {
		WriteAdvice(0);
		for(int j=0; j<cnt[i]; j++) WriteAdvice(1);
	}
}

#include "assistant.h"
#include<bits/stdc++.h>
using namespace std;

namespace assistant_var {
	int cnt[100005];
	int v[100005];
	int id[100005];
	bool inset[100005];
	queue<int> canthrow;
};

void Assist(unsigned char *A, int N, int K, int R) {
	using namespace assistant_var;
	int ptr = -1;
	for(int i = 0; i < K+N; i++) {
		ptr++;
		if(ptr>=R) break;
		while(ptr+1 < R && A[ptr+1]==1) {
			cnt[i]++;
			ptr++;
		}
	}
	for(int i = 0; i < K; i++) {
		v[i] = i;
		inset[i] = true;
		id[i] = i;
		if(cnt[i]==0) canthrow.push(i);
	}
	int timer = K;
	for(int i = 0; i < N; i++) {
		v[K+i] = GetRequest();
		if(inset[v[K+i]]) {
			cnt[id[v[K+i]]]--;
			if(cnt[id[v[K+i]]]==0) canthrow.push(v[K+i]);
		} else {
			PutBack(canthrow.front());
			inset[canthrow.front()] = false;
			inset[v[K+i]] = true;
			id[v[K+i]] = timer;
			canthrow.pop();
			if(cnt[timer]==0) canthrow.push(v[K+i]);
			timer++;
		}
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 67952 KB Output is correct
2 Correct 38 ms 67980 KB Output is correct
3 Correct 41 ms 68216 KB Output is correct
4 Correct 42 ms 68240 KB Output is correct
5 Correct 42 ms 68144 KB Output is correct
6 Correct 42 ms 68264 KB Output is correct
7 Correct 42 ms 68372 KB Output is correct
8 Correct 44 ms 68312 KB Output is correct
9 Correct 46 ms 68324 KB Output is correct
10 Correct 46 ms 68168 KB Output is correct
11 Correct 43 ms 68392 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 68596 KB Output is correct
2 Correct 81 ms 70820 KB Output is correct
3 Correct 161 ms 75440 KB Output is correct
4 Correct 119 ms 73736 KB Output is correct
5 Correct 116 ms 73972 KB Output is correct
6 Correct 130 ms 73908 KB Output is correct
7 Correct 146 ms 74712 KB Output is correct
8 Correct 125 ms 73848 KB Output is correct
9 Correct 102 ms 73728 KB Output is correct
10 Correct 152 ms 75244 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 72748 KB Output is correct
2 Correct 147 ms 75008 KB Output is correct
3 Correct 150 ms 75068 KB Output is correct
4 Correct 152 ms 75212 KB Output is correct
5 Correct 143 ms 74572 KB Output is correct
6 Correct 150 ms 75020 KB Output is correct
7 Correct 152 ms 75196 KB Output is correct
8 Correct 135 ms 74788 KB Output is correct
9 Correct 137 ms 74744 KB Output is correct
10 Correct 148 ms 75024 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 68276 KB Output is correct
2 Correct 43 ms 68204 KB Output is correct
3 Correct 44 ms 68160 KB Output is correct
4 Correct 40 ms 68264 KB Output is correct
5 Correct 44 ms 68072 KB Output is correct
6 Correct 47 ms 68080 KB Output is correct
7 Correct 43 ms 68196 KB Output is correct
8 Correct 46 ms 68396 KB Output is correct
9 Correct 46 ms 68408 KB Output is correct
10 Correct 50 ms 68368 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 73696 KB Output is correct - 120000 bits used
2 Correct 154 ms 73836 KB Output is correct - 122000 bits used
3 Correct 152 ms 73820 KB Output is correct - 125000 bits used
4 Correct 144 ms 73840 KB Output is correct - 125000 bits used
5 Correct 150 ms 73924 KB Output is correct - 125000 bits used
6 Correct 147 ms 73932 KB Output is correct - 125000 bits used
7 Correct 149 ms 73808 KB Output is correct - 124828 bits used
8 Correct 144 ms 73816 KB Output is correct - 124910 bits used
9 Correct 152 ms 73968 KB Output is correct - 125000 bits used
10 Correct 138 ms 73584 KB Output is correct - 125000 bits used