oj.uz

Submission #929373

# Submission time Handle Problem Language Result Execution time Memory
929373 2024-02-18T05:12:38 Z glitcher Rack (eJOI19_rack) C++14
40 / 100
 59 ms 33116 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 10 ms 2504 KB Output is correct
9 Correct 40 ms 8628 KB Output is correct
10 Correct 59 ms 33116 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 10 ms 2504 KB Output is correct
9 Correct 40 ms 8628 KB Output is correct
10 Correct 59 ms 33116 KB Output is correct
11 Runtime error 2 ms 604 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -