Submission #137734

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137734	2019-07-28T09:16:08 Z	임유진(#3281)	Bitwise (BOI06_bitwise)	C++14	100 / 100	2 ms	380 KB

bitwise

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;


int main() {
	ios::sync_with_stdio(0);
	int N, P;
	int K[MAXN], A[MAXN], B[MAXN];
	int sum[MAXN], mx[MAXN];
	bool all[MAXN];

	cin >> N >> P;
	for(int i = 0; i < P; i++) cin >> K[i];
	for(int i = 0; i < N; i++) cin >> A[i] >> B[i];

	sum[0] = 0;
	for(int i = 1; i <= P; i++) sum[i] = sum[i - 1] + K[i - 1];
	for(int i = 0; i < P; i++) all[i] = false;

	int ans = 0;
	for(int i = 30; i >= 0; i--) {
		bool b = true;
		for(int j = 0; j < P; j++) if(!all[j]) {
			mx[j] = -1;
			for(int k = sum[j]; k < sum[j + 1]; k++) if(B[k] >= (1 << i))
				if(mx[j] == -1 || A[k] >= (1 << i)) mx[j] = k;
			if(mx[j] == -1) {
				b = false;
				break;
			}
		}
		if(b) {
			ans += (1 << i);
			for(int j = 0; j < P; j++) if(!all[j]) A[mx[j]] = max(A[mx[j]], (1 << i));
		}
		for(int j = 0; j < P; j++) if(!all[j]) for(int k = sum[j]; k < sum[j + 1]; k++)
			if(A[k] < (1 << i) && (1 << i) <= B[k]) all[j] = true;
		for(int j = 0; j < P; j++) if(!all[j]) for(int k = sum[j]; k < sum[j + 1]; k++) if(A[k] >= (1 << i)) {
			A[k] -= (1 << i);
			B[k] -= (1 << i);
		}
	}

	cout << ans;
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	380 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct