oj.uz

Submission #199455

# Submission time Handle Problem Language Result Execution time Memory
199455 2020-02-01T12:54:24 Z TadijaSebez Bitwise (BOI06_bitwise) C++11
100 / 100
 6 ms 376 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=105;
const int L=31;
int n,m;
vector<int> my[N];
int l[N],r[N],st[N],ans[N];
bool done[N];
int main()
{
	scanf("%i %i",&n,&m);
	int sz=0;
	for(int i=1;i<=m;i++)
	{
		int k;
		scanf("%i",&k);
		for(int j=1;j<=k;j++) my[i].pb(sz+j);
		sz+=k;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%i %i",&l[i],&r[i]);
		for(int j=L-1;~j;j--)
		{
			if((l[i]>>j)==(r[i]>>j)) ans[i]+=r[i]&(1<<j);
			else{ st[i]=j;break;}
		}
	}
	int sol=0;
	for(int j=L-1;~j;j--)
	{
		bool ok=1;
		for(int i=1;i<=m;i++)
		{
			bool easy=0;
			int can=-1;
			for(int k:my[i])
			{
				if(ans[k]&(1<<j)) easy=1;
				if(st[k]>=j && !done[k])
				{
					if(r[k]>>j&1) can=k;
				}
			}
			if(!easy && can==-1) ok=0;
		}
		if(ok)
		{
			sol+=1<<j;
			for(int i=1;i<=m;i++)
			{
				bool easy=0;
				int can=-1;
				for(int k:my[i])
				{
					if(ans[k]&(1<<j)) easy=1;
					if(st[k]>=j && !done[k])
					{
						if(r[k]>>j&1) can=k;
					}
				}
				if(easy) can=-1;
				for(int k:my[i])
				{
					if(st[k]>=j && !done[k] && (r[k]>>j&1))
					{
						if(k==can)
						{
							ans[k]+=1<<j;
						}
						else
						{
							ans[k]+=(1<<j)-1;
							done[k]=1;
						}
					}
				}
			}
		}
		else
		{
			for(int i=1;i<=m;i++)
			{
				for(int k:my[i])
				{
					if(st[k]>=j && !done[k] && (r[k]>>j&1))
					{
						ans[k]+=(1<<j)-1;
						done[k]=1;
					}
				}
			}
		}
	}
	printf("%i\n",sol);
	return 0;
}

Compilation message

bitwise.cpp: In function 'int main()':
bitwise.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
bitwise.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&k);
   ~~~~~^~~~~~~~~
bitwise.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&l[i],&r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

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