Submission #643214

#	Time	Username	Problem	Language	Result	Execution time	Memory
643214		Kripton	Bitwise (BOI06_bitwise)	C++14	100 / 100	1 ms	312 KiB

bitwise

#include <bits/stdc++.h>
using namespace std;
int a[101],b[101],v[101];
vector <int> interes[101],newinteres;
int sure[31];
int main()
{
    int n,i,k,j,x;
    cin>>n>>k;
    for(i=1;i<=k;i++)
        cin>>v[i];
    for(i=1;i<=n;i++)
        cin>>a[i]>>b[i];
    int sum=0,l;
    for(l=1;l<=k;l++)
    {
        for(int x=1;x<=31;x++)
        {
            int sau=0,cnt=0;
            for(j=0;j<=30;j++)
                sure[j]=0;
            int highest=-1,ind;
            for(i=sum+1;i<=sum+v[l];i++)
            {
                for(j=30;j>=0;j--)
                {
                    if((a[i]&(1<<j))!=(b[i]&(1<<j)))
                        break;
                    if(a[i]&(1<<j))
                    {
                        sau|=(1<<j);
                        sure[j]++;
                    }
                }
                if(j>highest)
                {
                    highest=j;
                    ind=i;
                    cnt=1;
                }
                else if(j==highest)
                    cnt++;
            }
            if(highest==-1)
            {
                interes[l].push_back(sau);
                break;
            }
            if(sure[highest]!=0||cnt>=2)
            {
                interes[l].push_back(sau|((1<<(highest+1))-1));
                break;
            }
            interes[l].push_back(sau|((1<<highest)-1));
            a[ind]=(a[ind]|((1<<(highest+1))-1))^((1<<highest)-1);
        }
        sum+=v[l];
    }
    int r=0,pas=1<<30;
    while(pas)
    {
        int val=r+pas,ok=1;
        for(l=1;l<=k&&ok;l++)
        {
            ok=0;
            for(auto it:interes[l])
                if((val&it)==val)
                    ok=1;
        }
        if(ok)
        {
            r+=pas;
            for(l=1;l<=k;l++)
            {
                newinteres.clear();
                for(auto it:interes[l])
                    if((val&it)==val)
                        newinteres.push_back(it);
                interes[l]=newinteres;
            }
        }
        pas/=2;
    }
    cout<<r;
    return 0;
}

Compilation message (stderr)

bitwise.cpp: In function 'int main()':
bitwise.cpp:8:17: warning: unused variable 'x' [-Wunused-variable]
    8 |     int n,i,k,j,x;
      |                 ^
bitwise.cpp:55:19: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |             a[ind]=(a[ind]|((1<<(highest+1))-1))^((1<<highest)-1);
      |             ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100