TC (4*n)

#include<bits/stdc++.h>
#define null NULL
using namespace std;
int t,n,m,curr=0,mx1=0,mx2=0,mx3=0,x;
vector<int>a1,a2,a3;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>t;
while(t--)
{
    cin>>n>>m;
    //inputs for array
    for(int i=0;i<n;i++)
    {
        cin>>x;
        a1.push_back(x);
    }
    for(int i=0;i<n;i++)
    {
        cin>>x;
        a2.push_back(x);
    }
    for(int i=0;i<n;i++)
    {
        cin>>x;
        a3.push_back(x);
    }
    for(int i=0;i<n;i++)
    {
        if(mx1|a1[i]<=m)mx1=mx1|a1[i];
        else break;
    }
    for(int i=0;i<n;i++)
    {
        if(mx2|a2[i]<=m)mx2=mx2|a2[i];
        else break;
    }
    for(int i=0;i<n;i++)
    {
        if(mx3|a3[i]<=m)mx3=mx3|a3[i];
        else break;
    }
    if(mx1|mx2|mx3==m)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    mx1=mx2=mx3=0;
    a1.clear();
    a2.clear();
    a3.clear();
}
return 0;
}

ADD REPLY • link 3 months ago

Vaibhav Aggarwal • 0

Entering edit mode

#include#define ll long long #define f first #define s second #define all(c) c.begin(),c.end() #define FAST ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); using namespace std; void Result(){ ll n,m; cin>>n>>m; vectora(n), b(n), c(n); for (int i = 0; i < n; i++){ cin >> a[i]; if(i!=0){ a[i] |= a[i - 1]; } } for (int i = 0; i < n; i++){ cin >> b[i]; if(i!=0){ b[i] |= b[i - 1]; } } for (int i = 0; i < n; i++){ cin >> c[i]; if(i!=0){ c[i] |= c[i - 1]; } } string mb = ""; while(m>0){ mb += char(m % 2 + '0'); m /= 2; } reverse(all(mb)); string first = ""; for (int i = 0; i < n; i++){ string t = ""; ll d = a[i]; while(d>0){ t += char(d % 2 + '0'); d /= 2; } reverse(all(t)); if(t.length()>mb.length()){ break; } bool ok = 1; for (int i = t.length() - 1; i >= 0; i--){ if(mb[i]=='0' && t[i]=='1'){ ok = 0; } } if(ok){ first = t; } } string second = ""; for (int i = 0; i < n; i++){ string t = ""; ll d = b[i]; while(d>0){ t += char(d % 2 + '0'); d /= 2; } reverse(all(t)); if(t.length()>mb.length()){ break; } bool ok = 1; for (int i = t.length() - 1; i >= 0; i--){ if(mb[i]=='0' && t[i]=='1'){ ok = 0; } } if(ok){ second = t; } } string third = ""; for (int i = 0; i < n; i++){ string t = ""; ll d = c[i]; while(d>0){ t += char(d % 2 + '0'); d /= 2; } reverse(all(t)); if(t.length()>mb.length()){ break; } bool ok = 1; for (int i = t.length() - 1; i >= 0; i--){ if(mb[i]=='0' && t[i]=='1'){ ok = 0; } } if(ok){ third = t; } } string ans = ""; reverse(all(first)); reverse(all(second)); reverse(all(third)); while (first.length()!=mb.length()) { first += '0'; } while(second.length()!=mb.length()){ second += '0'; } while(third.length()!=mb.length()){ third += '0'; } reverse(all(first)); reverse(all(second)); reverse(all(third)); for (int i = 0; i < mb.length(); i++){ if(first[i]=='1'||second[i]=='1'||third[i]=='1'){ ans += '1'; } else{ ans += '0'; } } if(ans==mb) cout << "Yes" << endl; else cout << "No" << endl; } int main() { FAST int test=1; cin>>test; while(test--){ Result(); } return 0; }

ADD COMMENT • link 13 months ago Deepak • 0

Entering edit mode


#include <bits/stdc++.h>
using namespace std;

bool fun(int i1,int i2,int i3,int n,long long curr,int m,int arr1[],int arr2[],int arr3[])
{
    if(curr==m) return true;
    if(curr>m or i1>=n or i2>=n or i3>=n) return false;
    if(fun(i1+1,i2,i3,n,curr | arr1[i1],m,arr1,arr2,arr3)) return true;
    if(fun(i1,i2+1,i3,n,curr | arr2[i2],m,arr1,arr2,arr3)) return true;
    if(fun(i1,i2,i3+1,n,curr | arr3[i3],m,arr1,arr2,arr3)) return true;
    return false;
}

int main() 
{
	int t;
	cin>>t;
	while(t--)
	{
	    int n,m;
	    cin>>n>>m;
	    int arr1[n],arr2[n],arr3[n];
	    for(int i=0;i<n;i++) cin>>arr1[i];
	    for(int i=0;i<n;i++) cin>>arr2[i];
	    for(int i=0;i<n;i++) cin>>arr3[i];
	    if(fun(0,0,0,n,0,m,arr1,arr2,arr3)) cout<<"Yes"<<"\n";
	    else cout<<"No"<<"\n";
	}
	return 0;
}

ADD COMMENT • link 12 months ago Aarush • 0

Entering edit mode

3D DP

ADD COMMENT • link 12 months ago Ayush Agarwal • 20

Entering edit mode

Do we really need dp here? I mean, we can just do brute force to find the maximum depth that we can go into each stack just by maintaining for a given depth, does any set bit in 'm' appears in the OR of the preffix. Once we know the maximum depth, we can just tak the OR of all the numbers in every stack at lower depths than the maximum allowed depth. In the end if the result is equal to m then the answer is "Yes" else it is "No". Is this correct?

ADD COMMENT • link 12 months ago Anuron Avijit Das • 0

Entering edit mode

Exactly bhai , dp ki koi jarurat nhi hai, jab tk koi aisi bit na aye jisme (1ll<<i)&m==0 ho tb tk us stack ki book add karte jao, aise hi teeno stack mei karo, last me check karna hai ki m ban gaya ki nhi

ADD REPLY • link 12 months ago

Harshit Gupta • 0