Submission #929373

#	Time	Username	Problem	Language	Result	Execution time	Memory
929373		glitcher	Rack (eJOI19_rack)	C++14	40 / 100	59 ms	33116 KiB

rack

#include<bits/stdc++.h>                                           
using namespace std;
 
int n, k;
vector<int> a;
vector<long long> sum;
 
void build(int id, int L, int R) {
	if (L == R) {
		sum[id] = 0;
		return;
	}
	int M = (L + R) / 2, x = 2 * id + 1, y = 2 * id + 2;
	build(x, L, M);
	build(y, M + 1, R);
	sum[id] = sum[x] + sum[y];
}
 
void update(int id, int L, int R, int i) {
	if (L == R) {
		sum[id] = 1;
		return;
	}
	int M = (L + R) / 2, x = 2 * id + 1, y = x + 1;
	if (i <= M) {
		update(x, L, M, i);
	} else {
		update(y, M + 1, R, i);
	}
	sum[id] = sum[x] + sum[y];
}
 
long long query(int id, int L, int R) {
	int M = (L + R) / 2, x = 2 * id + 1, y = x + 1;
	//cout << id << " " << L << " " << R <<  " " << sum[x] << " " << sum[y] << endl;
	if (L == R) {
		return L;
	}

	if (sum[x] == sum[y]) 
		return query(x, L, M);
	return query(y, M + 1, R);
}
 
int main() {
	cin >> n >> k;
	long long lim = pow(2, n) - 1;
	sum.resize(4 * (pow(2, n)), 0);
	build(0, 0, n - 1);
	long long t;
	for(int i = 1; i <= k; i++){
		t = query(0, 0, lim) + 1;
		//cout << t << endl;
		update(0, 0, lim, t - 1);
	}
	cout << t;
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 60