oj.uz

Submission #577260

# Submission time Handle Problem Language Result Execution time Memory
577260 2022-06-14T11:21:12 Z Justin1 Last supper (IOI12_supper) C++14
0 / 100
 439 ms 84976 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);
		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 Runtime error 43 ms 68196 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 69 ms 69332 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 347 ms 81772 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 68080 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 Runtime error 433 ms 84472 KB Execution killed with signal 6
2 Runtime error 418 ms 84696 KB Execution killed with signal 6
3 Runtime error 425 ms 84828 KB Execution killed with signal 6
4 Runtime error 424 ms 84976 KB Execution killed with signal 6
5 Runtime error 424 ms 84788 KB Execution killed with signal 6
6 Runtime error 431 ms 84756 KB Execution killed with signal 6
7 Runtime error 415 ms 84840 KB Execution killed with signal 6
8 Runtime error 427 ms 84732 KB Execution killed with signal 6
9 Runtime error 439 ms 84924 KB Execution killed with signal 6
10 Runtime error 417 ms 84792 KB Execution killed with signal 6