Submission #307234

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
307234	2020-09-27T12:17:29 Z	Rainbowbunny	Bitwise (BOI06_bitwise)	C++17	100 / 100	1 ms	384 KB

bitwise

#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
using namespace std;
using cd = complex <double>;
 
const long long INF = 1e15;
const int N = 3e5 + 2;
//const int mod = 1e9 + 7;//998244353;//1e9 + 7;//786433;
const double Pi = acos(-1);
 
void Fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}
 
int n, p;
int res = 0;
bool ok[105];
vector <pair <int, int> > A[105];
 
signed main()
{
	cin >> n >> p;
	for(int i = 1; i <= p; i++)
	{
		int sz;
		cin >> sz;
		A[i].resize(sz);
	}
	for(int i = 1; i <= p; i++)
	{
		for(auto &x : A[i])
		{
			cin >> x.fi >> x.se;
		}
	}
	for(int i = 30; i >= 0; i--)
	{
		int temp = 1 << i;
		bool can = true; 
		for(int j = 1; j <= p; j++)
		{
			if(ok[j])
			{
				continue;
			}
			int cnt[4];
			cnt[0] = 0;
			cnt[1] = 0;
			cnt[2] = 0;
			for(auto x : A[j])
			{
				if(temp > x.se)
				{
					++cnt[0];
				}
				else if(x.fi >= temp)
				{
					++cnt[2];
				}
				else
				{
					++cnt[1];
				}
			}
			if(cnt[1] + cnt[2] == 0)
			{
				can = false;
			}
		}	
		if(can == false)
		{
			for(int j = 1; j <= p; j++)
			{
				for(auto &x : A[j])
				{
					if(x.fi >= temp)
					{
						x.fi -= temp;
						x.se -= temp;
					}
					else if(x.se >= temp)
					{
						x.se = temp - 1;
					}
				}
			}
		}
		else
		{
			res |= (1 << i);
			for(int j = 1; j <= p; j++)
			{
				if(ok[j])
				{
					continue;
				}
				int cnt[4];
				cnt[0] = 0;
				cnt[1] = 0;
				cnt[2] = 0;
				for(auto x : A[j])
				{
					if(temp > x.se)
					{
						++cnt[0];
					}
					else if(x.fi >= temp)
					{
						++cnt[2];
					}
					else
					{
						++cnt[1];
					}
				}
				if(cnt[1] + cnt[2] > 1 and cnt[1] > 0)
				{
					ok[j] = true;
				}
				else if(cnt[1] == 1)
				{
					for(auto &x : A[j])
					{
						if(x.se >= temp)
						{
							x.fi = 0;
							x.se = x.se - temp;
						}
					}
				}
				else if(cnt[1] == 0)
				{
					for(auto &x : A[j])
					{
						if(x.fi >= temp)
						{
							x.fi -= temp;
							x.se -= temp;
						}
					}
				}
			}	
		}
	}
	cout << res;
}

Subtask #1

100.0 / 100.0

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