oj.uz

Submission #761153

# Submission time Handle Problem Language Result Execution time Memory
761153 2023-06-19T09:29:47 Z NothingXD Last supper (IOI12_supper) C++17
43 / 100
 218 ms 17112 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 = max(1, 32 - __builtin_clz(K-1));
	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 = max(1, 32 - __builtin_clz(K-1));
	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));
		}
		ptr += lg;
		int idx = Find(x+1);
		PutBack(idx);
		Add(idx+1, -1);
		Mark[idx] = false;
		Mark[tmp] = true;
		Add(tmp+1, 1);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2948 KB Output is correct
2 Correct 1 ms 2964 KB Output is correct
3 Correct 3 ms 2948 KB Output is correct
4 Correct 4 ms 3236 KB Output is correct
5 Correct 4 ms 3372 KB Output is correct
6 Correct 8 ms 3444 KB Output is correct
7 Correct 4 ms 3364 KB Output is correct
8 Correct 10 ms 3560 KB Output is correct
9 Correct 12 ms 3552 KB Output is correct
10 Correct 8 ms 3508 KB Output is correct
11 Correct 9 ms 3404 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3892 KB Output is correct
2 Correct 69 ms 8032 KB Output is correct
3 Correct 210 ms 16264 KB Output is correct
4 Correct 131 ms 12532 KB Output is correct
5 Correct 177 ms 14532 KB Output is correct
6 Correct 191 ms 14852 KB Output is correct
7 Correct 175 ms 14712 KB Output is correct
8 Correct 191 ms 14672 KB Output is correct
9 Correct 101 ms 12064 KB Output is correct
10 Correct 163 ms 14416 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 12228 KB Output is correct
2 Correct 185 ms 14432 KB Output is correct
3 Correct 168 ms 14488 KB Output is correct
4 Correct 155 ms 14232 KB Output is correct
5 Correct 128 ms 13000 KB Output is correct
6 Correct 164 ms 14532 KB Output is correct
7 Correct 160 ms 14404 KB Output is correct
8 Correct 215 ms 16924 KB Output is correct
9 Correct 127 ms 13204 KB Output is correct
10 Correct 170 ms 14512 KB Output is correct

Subtask #4
0 / 35.0

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

Subtask #5
17.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 14648 KB Output is partially correct - 772365 bits used
2 Correct 169 ms 14580 KB Output is partially correct - 742095 bits used
3 Correct 166 ms 14476 KB Output is partially correct - 712470 bits used
4 Correct 172 ms 14684 KB Output is partially correct - 712005 bits used
5 Correct 176 ms 14408 KB Output is partially correct - 710610 bits used
6 Correct 165 ms 14480 KB Output is partially correct - 712155 bits used
7 Correct 169 ms 14596 KB Output is partially correct - 711090 bits used
8 Correct 166 ms 14516 KB Output is partially correct - 713340 bits used
9 Correct 162 ms 14500 KB Output is partially correct - 712830 bits used
10 Correct 218 ms 17112 KB Output is partially correct - 1117620 bits used