oj.uz

Submission #761140

# Submission time Handle Problem Language Result Execution time Memory
761140 2023-06-19T09:15:58 Z NothingXD Last supper (IOI12_supper) C++17
0 / 100
 219 ms 16864 KB 
#include<bits/stdc++.h>
#include "advisor.h"

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename H, typename... T>
void debug_out(H h, T... t){
	cerr << h << ' ';
	debug_out(t...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;

int n, lg, f[maxn];
bool mark[maxn];
vector<int> idx[maxn];
set<pii> q;
void add(int idx, int x){
	for (; idx <= n; idx += idx & -idx) f[idx] += x;
}

int get(int idx){
	int res = 0;
	for (; idx; idx -= idx & -idx) res += f[idx];
	return res;
}

void give(int x){
	for (int i = lg-1; ~i; i--){
		WriteAdvice((x >> i)&1);
	}
}

void ComputeAdvice(int *C, int N, int K, int M) {
	n = N;
	for (int i = 0; i < n; i++){
		idx[i].push_back(n);
	}
	for (int i = n-1; ~i; i--){
		idx[C[i]].push_back(i);
	}
	for (int i = 0; i < K; i++){
		q.insert({idx[i].back(), i});
		mark[i] = true;
		add(i+1, 1);
	}
	lg = 32 - __builtin_clz(K);
	for (int i = 0; i < n; i++){
		if (mark[C[i]]){
			q.erase({idx[C[i]].back(), C[i]});
			idx[C[i]].pop_back();
			q.insert({idx[C[i]].back(), C[i]});
			continue;
		}
		auto it = q.end();
		it--;
		pii tmp = *it;
		q.erase(it);
		idx[C[i]].pop_back();
		q.insert({idx[C[i]].back(), C[i]});
		give(get(tmp.S));
		add(tmp.S+1, -1);
		mark[tmp.S] = false;
		add(C[i]+1, 1);
		mark[C[i]] = true;
	}
}

#include<bits/stdc++.h>
#include "assistant.h"

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

/*void debug_out(){cerr << endl;}

template<typename H, typename... T>
void debug_out(H h, T... t){
	cerr << h << ' ';
	debug_out(t...);
}*/

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;

int nn, F[maxn];
bool Mark[maxn];

void Add(int idx, int x){
	for (; idx <= nn; idx += idx & -idx) F[idx] += x;
}

int Find(int idx){
	int res = 0;
	for (int i = 19; ~i; i--){
		int tmp = res + (1 << i);
		if (tmp <= nn && F[tmp] < idx){
			idx -= F[tmp];
			res = tmp;
		}
	}
	return res;
}

void Assist(unsigned char *A, int N, int K, int R) {
	nn = N;
	int lg = 32 - __builtin_clz(K);
	for (int i = 0; i < K; i++){
		Mark[i] = true;
		Add(i+1, 1);
	}
	int ptr = 0;
	for (int i = 0; i < nn; i++){
		int tmp = GetRequest();
		if (Mark[tmp]) continue;
		int x = 0;
		for (int j = ptr; j < ptr + lg; j++){
			x += (A[j] << (ptr + lg - j - 1));
		}
		int idx = Find(x+1);
		PutBack(idx);
		Add(idx+1, -1);
		Mark[idx] = false;
		Mark[tmp] = true;
		Add(tmp+1, 1);
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2948 KB Output is correct
2 Incorrect 1 ms 3008 KB Output isn't correct - not an optimal way
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 3896 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 12264 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3080 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 190 ms 14712 KB Output isn't correct - not an optimal way
2 Incorrect 173 ms 14672 KB Output isn't correct - not an optimal way
3 Incorrect 167 ms 14540 KB Output isn't correct - not an optimal way
4 Incorrect 199 ms 14436 KB Output isn't correct - not an optimal way
5 Incorrect 186 ms 14656 KB Output isn't correct - not an optimal way
6 Incorrect 176 ms 14476 KB Output isn't correct - not an optimal way
7 Incorrect 167 ms 14428 KB Output isn't correct - not an optimal way
8 Incorrect 172 ms 14512 KB Output isn't correct - not an optimal way
9 Incorrect 175 ms 14604 KB Output isn't correct - not an optimal way
10 Incorrect 219 ms 16864 KB Output isn't correct - not an optimal way