Submission #137586

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137586	2019-07-28T07:04:12 Z	윤교준(#3280)	Bitwise (BOI06_bitwise)	C++14	100 / 100	6 ms	380 KB

bitwise

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int B[105], C[105];
int A[105];

int N, K, Ans;

bool isp(int s, int e, int X) {
	vector<pii> V;
	for(int i = s; i <= e; i++) V.eb(B[i], C[i]);
	for(int key = 1<<30; key; key >>= 1) {
		if(X & key) {
			vector<pii> T, MustV, MayV;
			for(auto &v : V) {
				int s, e; tie(s, e) = v;
				if(e < key) T.eb(s, e);
				else if(key <= s) MustV.eb(s^key, e^key);
				else MayV.eb(s, e);
			}
			V = T;
			if(MustV.empty() && MayV.empty()) return false;
			if(!MustV.empty()) {
				for(auto &v : MustV) V.eb(v);
				for(auto &v : MayV) V.eb(v.first, key-1);
				continue;
			}
			sorv(MayV);
			V.eb(0, MayV.back().second^key);
			MayV.pop_back();
			for(auto &v : MayV) V.eb(v.first, key-1);
		} else {
			vector<pii> T;
			for(auto &v : V) {
				int s, e; tie(s, e) = v;
				if(key <= s) T.eb(s^key, e^key);
				else if(key <= e) T.eb(s, key-1);
				else T.eb(s, e);
			}
			swap(V, T);
		}
	}
	return true;
}

bool isp(int X) {
	for(int i = 1, s = 1, e; i <= K; i++) {
		e = s + A[i] - 1;
		if(!isp(s, e, X)) return false;
		s = e+1;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N >> K;
	for(int i = 1; i <= K; i++) cin >> A[i];
	for(int i = 1; i <= N; i++) cin >> B[i] >> C[i];
	for(int key = 1<<30; key; key >>= 1)
		if(isp(Ans | key)) Ans |= key;
	cout << Ans << endl;
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 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	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	3 ms	376 KB	Output is correct
12	Correct	3 ms	376 KB	Output is correct
13	Correct	4 ms	376 KB	Output is correct
14	Correct	3 ms	376 KB	Output is correct
15	Correct	3 ms	376 KB	Output is correct
16	Correct	6 ms	376 KB	Output is correct
17	Correct	5 ms	376 KB	Output is correct
18	Correct	6 ms	376 KB	Output is correct
19	Correct	6 ms	380 KB	Output is correct
20	Correct	5 ms	376 KB	Output is correct