oj.uz

Submission #643214

# Submission time Handle Problem Language Result Execution time Memory
643214 2022-09-21T13:59:46 Z Kripton Bitwise (BOI06_bitwise) C++14
100 / 100
 1 ms 312 KB 
#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

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.0 / 100.0

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