Find XOR (FINXOR) - Video EDITORIAL

editorial
, , , ,
1

Question Link - CodeChef: Practical coding for everyone
Solution Link - CodeChef: Practical coding for everyone

Editorial - Find XOR (FINXOR) | Editorial | SEPT'20 Long Challenge | CodeChef | Competitive Programming - YouTube

C++

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#define pb push_back
#define pr pair<int,int>
#define ld long double

int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);

int t;
 //t=1;
cin>>t;
while(t--){
    int n;
    cin>>n;
    bool flag=0;

    //query to calculate total sum of sequence
    cout<<1<<" "<<(1ll<<20)<<"\n";
    cout.flush();
    int tot;
    cin>>tot;
    tot-=(1ll<<20)*n;
    //tot is sum of the sequence
    int ans=0;

    vector<int>save(20,0);

    for(int bit=0;bit<=18;bit++){
        //num is k
        int num=(1ll<<bit);
        cout<<1<<" "<<num<<"\n";
        cout.flush();
        int x;
        cin>>x;
        //calculate difference
        //(sum of sequence - current sum)=(no. of 1's -no. of 0's)*(2^current bit)
        //(no. of 1's + no. of 0's)=n
        int diff=(tot-x)/num;

        save[bit]=(n+diff)/2;
        if(save[bit]&1){
            ans|=num;
        }
    }
    int sum=0;
    for(int i=0;i<=18;i++){
        sum+=(1ll<<i)*save[i];
    }
    int diff=(tot-sum)/(1ll<<19);
    save[19]=diff;
    if(diff&1)
        ans|=(1ll<<19);

    cout<<2<<" "<<ans<<"\n";
    cout.flush();
    int x;
    cin>>x;
}

}
``

1 Like