oj.uz

Submission #578978

# Submission time Handle Problem Language Result Execution time Memory
578978 2022-06-18T09:09:06 Z Justin1 Last supper (IOI12_supper) C++14
100 / 100
 627 ms 155160 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#include "advisor.h"
using namespace std;

int endK[25005], endN[100005];
int endpos[100005];
deque<int> pos[100005];
set<int> pos2[100005];

string dectobin(int x, int mx) {
	string res = "";
	for (int i = mx; i >= 0; i--) {
		if ((1 << i) & x) res += '1';
		else res += '0';
	}
	return res;
}

void ComputeAdvice(int *C, int N, int K, int M) {
	if (M == 2'000'000) {
		int mx = log2(N-1);
		for (int i = 0; i < N; i++) {
			string tmp = dectobin(C[i],mx);
			for (auto j : tmp) WriteAdvice(j-'0');
		}
		return;
	}
	set<pair<int,int>> scaffold;
	for (int i = 0; i < K; i++) scaffold.insert({i,-1});
	for (int i = 0; i < N; i++) endN[i] = -1;
	for (int i = 0; i < N; i++) pos[C[i]].push_back(i);
	for (int i = 0; i < N; i++) pos[i].push_back(1e9);
	for (int i = 0; i < N; i++) {
		for (auto j : pos[i]) pos2[i].insert(j);
	}
	set<pair<int,int>> cur;
	for (int i = 0; i < K; i++) cur.insert({pos[i][0],i});
	for (int i = 0; i < N; i++) {
		string tmp;
		if (cur.find({pos[C[i]][0],C[i]}) != cur.end()) {
			cur.erase({pos[C[i]][0],C[i]});
			pos[C[i]].pop_front();
			cur.insert({pos[C[i]][0],C[i]});
		} else {
			pos[C[i]].pop_front();
			int tar = (*cur.rbegin()).s;
			auto tmp = *scaffold.lower_bound({tar,INT_MIN});
			if (tmp.s == -1) endK[tmp.f] = i;
			else endN[tmp.s] = i;
			scaffold.erase(scaffold.find(tmp));
			scaffold.insert({C[i],i});
			cur.erase(*cur.rbegin());
			cur.insert({pos[C[i]][0],C[i]});
		}
	}
	for (auto i : scaffold) {
		if (i.s == -1) endK[i.f] = 1e8;
		else endN[i.s] = 1e8;
	}
	for (int i = 0; i < K; i++) {
		endpos[i] = endK[i];
		int tmp = *pos2[i].lower_bound(0);
		WriteAdvice(tmp > endK[i]);
	}
	for (int i = 0; i < N; i++) {
		if (endN[i] == -1) {
			int tmp = *pos2[C[i]].upper_bound(i);
			WriteAdvice(tmp > endpos[C[i]]);
		} else {
			int tmp = *pos2[C[i]].upper_bound(i);
			WriteAdvice(tmp > endN[i]);
			endpos[C[i]] = endN[i];
		}
	}
}
#include <bits/stdc++.h>
#define f first
#define s second
#include "assistant.h"
using namespace std;
 
deque<int> put;
int col[100005];
int C[100005];
 
void Assist(unsigned char *A, int N, int K, int R) {
	if (R > N+K) {
		deque<int> pos[100005];
		int lg = log2(N-1)+1;
		for (int i = 0; i < R; i++) {
			C[i/lg] += (1 << (lg - i % lg - 1)) * A[i];
		}
		for (int i = 0; i < N; i++) pos[C[i]].push_back(i);
		for (int i = 0; i < N; i++) pos[i].push_back(1e9);
		set<pair<int,int>> cur;
		for (int i = 0; i < K; i++) cur.insert({pos[i][0],i});
		for (int i = 0; i < N; i++) {
			GetRequest();
			if (cur.find({pos[C[i]][0],C[i]}) != cur.end()) {
				cur.erase({pos[C[i]][0],C[i]});
				pos[C[i]].pop_front();
				cur.insert({pos[C[i]][0],C[i]});
			} else {
				pos[C[i]].pop_front();
				PutBack((*cur.rbegin()).s);
				cur.erase(*cur.rbegin());
				cur.insert({pos[C[i]][0],C[i]});
			}
		}
		return;
	}
	for (int i = 0; i < K; i++) if (A[i]) put.push_back(i);
	for (int i = 0; i < K; i++) col[i] = 1;
	for (int i = K; i < R; i++) {
		int cur = GetRequest();
		if (col[cur]) {
			if (A[i]) put.push_back(cur);
			continue;
		}
		PutBack(put[0]);
		col[put[0]] = 0;
		col[cur] = 1;
		put.pop_front();
		if (A[i]) put.push_back(cur);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 80304 KB Output is correct
2 Correct 47 ms 80712 KB Output is correct
3 Correct 49 ms 80628 KB Output is correct
4 Correct 48 ms 80832 KB Output is correct
5 Correct 53 ms 81100 KB Output is correct
6 Correct 48 ms 81052 KB Output is correct
7 Correct 51 ms 81140 KB Output is correct
8 Correct 49 ms 81152 KB Output is correct
9 Correct 55 ms 81104 KB Output is correct
10 Correct 55 ms 81236 KB Output is correct
11 Correct 52 ms 81108 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 141156 KB Output is correct
2 Correct 284 ms 146012 KB Output is correct
3 Correct 558 ms 154112 KB Output is correct
4 Correct 560 ms 153716 KB Output is correct
5 Correct 528 ms 153740 KB Output is correct
6 Correct 627 ms 153940 KB Output is correct
7 Correct 542 ms 154448 KB Output is correct
8 Correct 502 ms 152856 KB Output is correct
9 Correct 510 ms 153452 KB Output is correct
10 Correct 520 ms 155160 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 93044 KB Output is correct
2 Correct 229 ms 96228 KB Output is correct
3 Correct 229 ms 96288 KB Output is correct
4 Correct 246 ms 96244 KB Output is correct
5 Correct 207 ms 95580 KB Output is correct
6 Correct 237 ms 96332 KB Output is correct
7 Correct 221 ms 96384 KB Output is correct
8 Correct 223 ms 96328 KB Output is correct
9 Correct 197 ms 96416 KB Output is correct
10 Correct 220 ms 96244 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 81240 KB Output is correct
2 Correct 51 ms 81140 KB Output is correct
3 Correct 55 ms 81056 KB Output is correct
4 Correct 53 ms 81184 KB Output is correct
5 Correct 52 ms 81300 KB Output is correct
6 Correct 55 ms 81100 KB Output is correct
7 Correct 65 ms 81148 KB Output is correct
8 Correct 51 ms 81296 KB Output is correct
9 Correct 54 ms 81184 KB Output is correct
10 Correct 56 ms 81396 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 95880 KB Output is correct - 120000 bits used
2 Correct 249 ms 96000 KB Output is correct - 122000 bits used
3 Correct 231 ms 96264 KB Output is correct - 125000 bits used
4 Correct 245 ms 96300 KB Output is correct - 125000 bits used
5 Correct 221 ms 96292 KB Output is correct - 125000 bits used
6 Correct 268 ms 96332 KB Output is correct - 125000 bits used
7 Correct 215 ms 96296 KB Output is correct - 124828 bits used
8 Correct 267 ms 96276 KB Output is correct - 124910 bits used
9 Correct 224 ms 96572 KB Output is correct - 125000 bits used
10 Correct 220 ms 96244 KB Output is correct - 125000 bits used