oj.uz

Submission #577263

# Submission time Handle Problem Language Result Execution time Memory
577263 2022-06-14T11:23:45 Z Justin1 Last supper (IOI12_supper) C++14
34 / 100
 471 ms 84868 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#include "advisor.h"
using namespace std;

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;
}

int seg[400005];

int qry(int t1, int t2, int id, int l, int r) {
	if (r < t1 || t2 < l) return 0;
	if (t1 <= l && r <= t2) return seg[id];
	int mid = (l+r)/2;
	return qry(t1,t2,id*2,l,mid)+qry(t1,t2,id*2+1,mid+1,r);
}

void upd(int tar, int val, int id, int l, int r) {
	if (l == r) {
		seg[id] = val;
		return;
	}
	int mid = (l+r)/2;
	if (tar <= mid) upd(tar,val,id*2,l,mid);
	else upd(tar,val,id*2+1,mid+1,r);
	seg[id] = seg[id*2] + seg[id*2+1];
}

void ComputeAdvice(int *C, int N, int K, int M) {
	int mx = log2(K-1);
	for (int i = 0; i < K; i++) upd(i,1,1,0,N-1);
	deque<int> pos[100005];
	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++) {
		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]});
			tmp = dectobin(0,mx);
		} else {
			pos[C[i]].pop_front();
			int tar = (*cur.rbegin()).s;
			upd(tar,0,1,0,N-1);
			tmp = dectobin(qry(0,tar,1,0,N-1),mx);
			upd(C[i],1,1,0,N-1);
			cur.erase(*cur.rbegin());
			cur.insert({pos[C[i]][0],C[i]});
		}
		for (auto j : tmp) WriteAdvice(j-'0');
	}
}

#include <bits/stdc++.h>
#define f first
#define s second
#include "assistant.h"
using namespace std;

int res[100005];
int used[100005];
int segtree[400005];

int binsearch(int tar, int id, int l, int r) {
	if (l == r) return l;
	int mid = (l+r)/2;
	if (tar < segtree[id*2]) return binsearch(tar,id*2,l,mid);
	else return binsearch(tar-segtree[id*2],id*2+1,mid+1,r);
}

void update(int tar, int val, int id, int l, int r) {
	if (l == r) {
		segtree[id] = val;
		return;
	}
	int mid = (l+r)/2;
	if (tar <= mid) update(tar,val,id*2,l,mid);
	else update(tar,val,id*2+1,mid+1,r);
	segtree[id] = segtree[id*2] + segtree[id*2+1];
}

void Assist(unsigned char *A, int N, int K, int R) {
	int lg = log2(K-1)+1;
	for (int i = 0; i < R; i++) {
		res[i/lg] += (1 << (lg - i % lg - 1)) * A[i];
	}
	for (int i = 0; i < K; i++) {
		used[i] = 1;
		update(i,1,1,0,N-1);
	}
	for (int i = 0; i < N; i++) {
		int cur = GetRequest();
		if (used[cur]) continue;
		int tmp = binsearch(res[i],1,0,N-1);
		assert(used[tmp]);
		PutBack(tmp);
		used[tmp] = 0;
		used[cur] = 1;
		update(tmp,0,1,0,N-1);
		update(cur,1,1,0,N-1);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68004 KB Output is correct
2 Correct 41 ms 67960 KB Output is correct
3 Correct 46 ms 68036 KB Output is correct
4 Correct 50 ms 68224 KB Output is correct
5 Correct 47 ms 68140 KB Output is correct
6 Correct 53 ms 68532 KB Output is correct
7 Correct 51 ms 68440 KB Output is correct
8 Correct 65 ms 68652 KB Output is correct
9 Correct 55 ms 68432 KB Output is correct
10 Correct 57 ms 68676 KB Output is correct
11 Correct 57 ms 68780 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 69216 KB Output is correct
2 Correct 201 ms 74620 KB Output is correct
3 Correct 468 ms 84868 KB Output is correct
4 Correct 292 ms 76784 KB Output is correct
5 Correct 354 ms 79284 KB Output is correct
6 Correct 418 ms 81300 KB Output is correct
7 Correct 433 ms 83268 KB Output is correct
8 Correct 392 ms 81616 KB Output is correct
9 Correct 224 ms 75476 KB Output is correct
10 Correct 434 ms 83688 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 80312 KB Output is correct
2 Correct 429 ms 83368 KB Output is correct
3 Correct 443 ms 83524 KB Output is correct
4 Correct 432 ms 83460 KB Output is correct
5 Correct 406 ms 83092 KB Output is correct
6 Correct 436 ms 83460 KB Output is correct
7 Correct 432 ms 83556 KB Output is correct
8 Correct 463 ms 83712 KB Output is correct
9 Correct 400 ms 83464 KB Output is correct
10 Correct 431 ms 83640 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 67984 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 82644 KB Output is partially correct - 1500000 bits used
2 Correct 441 ms 82912 KB Output is partially correct - 1500000 bits used
3 Correct 431 ms 82884 KB Output is partially correct - 1500000 bits used
4 Correct 428 ms 82972 KB Output is partially correct - 1500000 bits used
5 Correct 437 ms 82928 KB Output is partially correct - 1500000 bits used
6 Correct 440 ms 83000 KB Output is partially correct - 1500000 bits used
7 Correct 432 ms 82840 KB Output is partially correct - 1497585 bits used
8 Correct 457 ms 82868 KB Output is partially correct - 1500000 bits used
9 Correct 433 ms 82880 KB Output is partially correct - 1500000 bits used
10 Correct 441 ms 82932 KB Output is partially correct - 1500000 bits used