Distributed Code Jam 2017 Round 1 C. weird_editor

weird_editor.cpp

#include "message.h"
#include "weird_editor.h"
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    long long N  = NumberOfNodes();
    long long ID = MyNodeId();

    long long n = GetNumberLength();
    long long w = (n+N-1)/N;
    long long l = ID*w;
    long long r = min(ID*w+w, n);

    long long c[10] = {};
    for (long long i=l; i<r; i++)
    {
        long long d = GetDigit(i);
        c[d]++;
        for (long long j=d-1; j>=0; j--)
            c[j] = 0;
    }

    //for (int i=1; i<10; i++)
    //    cerr<<c[i]<<endl;

    for (int i=1; i<10; i++)
        PutLL(0, c[i]);
    Send(0);

    if (ID == 0)
    {
        long long C[10] = {};
        for (int i=0; i<N; i++)
        {
            long long c[10];
            Receive(i);
            for (int j=1; j<10; j++)
                c[j] = GetLL(i);

            //cerr<<i;
            //for (int j=1; j<10; j++)
            //    cerr<<" "<<c[j];
            //cerr<<endl;

            for (int j=9; j>=1; j--)
            {
                C[j] += c[j];
                if (c[j]>0)
                    for (int k=j-1; k>=0; k--)
                        C[k] = 0;
            }
        }

        //for (int i=1; i<10; i++)
        //    cerr<<C[i]<<endl;

        for (int i=0; i<N; i++)
        {
            for (int j=1; j<10; j++)
                //cerr<<j<<" "<<C[j]<<endl,
                PutLL(i, C[j]);
            Send(i);
        }
    }

    Receive(0);
    long long C[10];
    for (int i=1; i<10; i++)
        C[i] = GetLL(0);
    
    long long ans = 0LL;
    long long M = 1000000007;
    long long t = 0;
    for (int i=9; i>=1; i--)
    {
        for (long long j=max(l, t); j<min(r, t+C[i]); j++)
            ans = (ans*10 + i) % M;
        t += C[i];
    }
    for (long long i=t; i<r; i++)
        ans = ans*10%M;

    long long num0 = n - r;
    long long z = 10;
    long long m0 = 1;
    for (long long i=0; i<60; i++)
    {
        if (num0>>i&1)
            m0 = m0*z%M;
        z = z*z%M;
    }
    ans = ans*m0%M;
    
    //cerr<<ans<<endl;

    PutLL(0, ans);
    Send(0);

    if (ID==0)
    {
        long long ans = 0;
        for (int i=0; i<N; i++)
        {
            Receive(i);
            ans = (ans + GetLL(i)) % M;
        }
        cout<<ans<<endl;
    }

    return 0;
}