Distributed Code Jam 2017 Round 2 D

broken_memory.cpp

#include "message.h"
#include "broken_memory.h"
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int main() {
    long long N  = NumberOfNodes();
    if (N%2 != 0)
    {
        cerr<<"error"<<endl;
        return 0;
    }
    long long ID = MyNodeId();

    long long n = GetLength();
    static long long v[10000000];
    for (long long i=0; i<n; i++)
        v[i] = GetValue(i);

    if (ID%2 != 0)
    {
        while (true)
        {
            Receive(ID^1);
            long long l = GetLL(ID^1);
            long long r = GetLL(ID^1);
            if (l==-1LL)
                break;
            long long s = 0;
            long long x = 0;
            for (long long i=l; i<r; i++)
                s += v[i],
                x ^= v[i];
            PutLL(ID^1, s);
            PutLL(ID^1, x);
            Send(ID^1);
        }
    }
    else
    {
        long long l = 0;
        long long r = n;
        while (r-l>1)
        {
            long long m = (l+r)/2;

            PutLL(ID^1, l);
            PutLL(ID^1, m);
            Send(ID^1);

            long long s = 0;
            long long x = 0;
            for (long long i=l; i<m; i++)
                s += v[i],
                x ^= v[i];

            Receive(ID^1);
            long long so = GetLL(ID^1);
            long long xo = GetLL(ID^1);

            if (s != so || x != xo)
                r = m;
            else
                l = m;
        }
        long long ans1 = l;

        PutLL(ID^1, 0);
        PutLL(ID^1, n);
        Send(ID^1);

        long long pss = 0;
        long long pxs = 0;
        for (long long i=0; i<n; i++)
            pss += v[i],
            pxs ^= v[i];

        Receive(ID^1);
        long long pso = GetLL(ID^1);
        long long pxo = GetLL(ID^1);

        l = 0;
        r = n;
        while (r-l>1)
        {
            long long m = (l+r)/2;

            PutLL(ID^1, l);
            PutLL(ID^1, m);
            Send(ID^1);

            long long sls = 0;
            long long xls = 0;
            for (long long i=l; i<m; i++)
                sls += v[i],
                xls ^= v[i];

            Receive(ID^1);
            long long slo = GetLL(ID^1);
            long long xlo = GetLL(ID^1);

            long long srs = pss - sls;
            long long xrs = pxs ^ xls;
            long long sro = pso - slo;
            long long xro = pxo ^ xlo;

            //if (ID==0)
            //{
            //    cerr<<l<<" "<<m<<" "<<r<<" "<<sls<<" "<<slo<<" "<<xls<<" "<<xlo<<" "<<srs<<" "<<sro<<" "<<xrs<<" "<<xro<<" "<<ans1<<endl;
            //}

            if (srs == sro && xrs == xro)
            {
                r = m;
                pss = sls;
                pxs = xls;
                pso = slo;
                pxo = xlo;
            }
            else
            {
                l = m;
                pss = srs;
                pxs = xrs;
                pso = sro;
                pxo = xro;
            }
        }

        PutLL(ID^1, -1LL);
        PutLL(ID^1, -1LL);
        Send(ID^1);

        if (ID==2)
        {
            Receive(0);
            long long p = GetLL(0);
            PutLL(0, v[p]);
            Send(0);
        }

        PutLL(0, ans1);
        PutLL(0, v[ans1]);
        PutLL(0, l);
        PutLL(0, v[l]);
        Send(0);
    }

    if (ID==0)
    {
        for (long long i=0; i<N; i+=2)
        {
            Receive(i);
            long long a1 = GetLL(i);
            long long v1 = GetLL(i);
            long long a2 = GetLL(i);
            long long v2 = GetLL(i);

            if (i==0)
            {
                PutLL(2, a1);
                Send(2);
                Receive(2);
                long long t = GetLL(2);
                if (v1 == t)
                    swap(a1, a2);
            }
            else
            {
                if (v1 == v[a1])
                    swap(a1, a2);
            }

            cout<<(i==0 ? "" : " ")<<a1<<" "<<a2;
        }
        cout<<endl;
    }

    return 0;
}