Submission #199455

#	Time	Username	Problem	Language	Result	Execution time	Memory
199455		TadijaSebez	Bitwise (BOI06_bitwise)	C++11	100 / 100	6 ms	376 KiB

bitwise

#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 (stderr)

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 / 100