oj.uz

Submission #577259

# Submission time Handle Problem Language Result Execution time Memory
577259 2022-06-14T11:19:28 Z Justin1 Last supper (IOI12_supper) C++14
0 / 100
 457 ms 83356 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);
		PutBack(tmp);
		update(tmp,0,1,0,N-1);
		update(cur,1,1,0,N-1);
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 67952 KB Output is correct
2 Incorrect 42 ms 67944 KB Error - Putting back a color when it is already on the scaffold
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 69220 KB Error - Putting back a color when it is already on the scaffold
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 348 ms 80476 KB Error - Putting back a color when it is already on the scaffold
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 426 ms 82720 KB Error - Putting back a color when it is already on the scaffold
2 Incorrect 418 ms 82876 KB Error - Putting back a color when it is already on the scaffold
3 Incorrect 414 ms 83164 KB Error - Putting back a color when it is already on the scaffold
4 Incorrect 418 ms 83356 KB Error - Putting back a color when it is already on the scaffold
5 Incorrect 420 ms 83032 KB Error - Putting back a color when it is already on the scaffold
6 Incorrect 420 ms 83068 KB Error - Putting back a color when it is already on the scaffold
7 Incorrect 425 ms 83048 KB Error - Putting back a color when it is already on the scaffold
8 Incorrect 422 ms 83216 KB Error - Putting back a color when it is already on the scaffold
9 Incorrect 412 ms 83344 KB Error - Putting back a color when it is already on the scaffold
10 Incorrect 457 ms 83116 KB Error - Putting back a color when it is already on the scaffold