Submission #137904

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
137904	2019-07-28T13:45:03 Z	onjo0127	Bitwise (BOI06_bitwise)	C++11	100 / 100	2 ms	380 KB

bitwise

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

int N, P;
long long A[109], B[109];
vector<int> S[109];

int main() {
	scanf("%d%d",&N,&P);
	for(int i=1, j=1; i<=P; i++) {
		int foo; scanf("%d",&foo);
		while(foo--) S[i].push_back(j++);
	}
	for(int i=1; i<=N; i++) scanf("%lld%lld",&A[i],&B[i]);
	long long ans = 0;
	for(int i=31; i>=0; i--) {
		bool f = 1;
		vector<int> T;
		for(int j=1; j<=P; j++) {
			bool l = 0;
			int mx = -1, mxi = -1;
			for(auto& it: S[j]) {
				if(A[it] & (1LL << i)) l = 1;
				else {
					long long tmp = A[it] + (1LL << i);
					for(int k=i-1; k>=0; k--) if(tmp & (1LL << k)) tmp -= (1LL << k);
					if(mx < B[it] - tmp) mx = B[it] - tmp, mxi = it;
				}
			}
			if(l) mxi = -1;
			else {
				if(mxi != -1) {
					l = 1;
					T.push_back(mxi);
				}
				else l = 0;
			}
			f &= l;
		}
		if(f) {
			ans += (1LL << i);
			for(auto& it: T) {
				long long tmp = A[it] + (1LL << i);
				for(int k=i-1; k>=0; k--) if(tmp & (1LL << k)) tmp -= (1LL << k);
				A[it] = tmp, B[it] = min(tmp + (1LL << i) - 1, B[it]);
			}
		}
	}
	printf("%lld", ans);
	return 0;
}

Compilation message

bitwise.cpp: In function 'int main()':
bitwise.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&N,&P);
  ~~~~~^~~~~~~~~~~~~~
bitwise.cpp:11:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int foo; scanf("%d",&foo);
            ~~~~~^~~~~~~~~~~
bitwise.cpp:14:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%lld%lld",&A[i],&B[i]);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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	380 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	380 KB	Output is correct
7	Correct	2 ms	380 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	256 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	256 KB	Output is correct
14	Correct	2 ms	256 KB	Output is correct
15	Correct	2 ms	256 KB	Output is correct
16	Correct	2 ms	256 KB	Output is correct
17	Correct	2 ms	256 KB	Output is correct
18	Correct	2 ms	256 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct