java-competitive/dcj/tasks/weird_editor/Main.java

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class Main {

  public static void main(String[] args) {
    new Main().run();
  }

  int myId = message.MyNodeId();
  int nodeCount = message.NumberOfNodes();
  long numberLength = weird_editor.GetNumberLength();
  long perNode = numberLength / nodeCount + 1;

  long iL = Math.min(myId * perNode, numberLength);
  long iR = Math.min((myId + 1) * perNode, numberLength);

  void run() {
    client();

    if (myId == 0) {
      server();
    }
  }

  long mul(long a, long b) {
    return (a * b) % MOD;
  }

  long add(long a, long b) {
    return (a + b) % MOD;
  }

  long merge(long res1, long l1, long res2, long l2) {
    return add(mul(res1, pow(10, l2)), res2);
  }

  long calcSeries(long digit, int n) {
    long res = 0;
    long d = 1;

    for (int i = 0; i < n; i++) {
      res = add(res, mul(d, digit));
      d = mul(d, 10);
    }
    return res;
  }

  long MOD = 1000000007L;

  long pow(long a, long n) {
    if (n == 0) {
      return 1 % MOD;
    }
    if (n == 1) {
      return a % MOD;
    }
    if (n % 2 == 0) {
      long x = pow(a, n / 2);
      return mul(x, x);
    }
    return mul(pow(a, n - 1), a);
  }

  void client() {
//    System.out.println("[" + iL + ", " + iR + "]");

    List<Long> digits = new ArrayList<>();
    for (long i = iL; i < iR; i++) {
      long x = weird_editor.GetDigit(i);
      digits.add(x);
    }

    List<Long> res = new ArrayList<>();

    long[] counts = new long[10];

    int rightmost = -1;
    for (int digit = 9; digit >= 1; digit--) {
      for (int i = rightmost + 1; i < digits.size(); i++) {
        if (digits.get(i) == digit) {
          counts[digit]++;
          rightmost = i;
        }
      }
    }

    long[] ress = new long[10];
    long[] ressLen = new long[10];
    for (int i = 0; i < 10; i++) {
      ress[i] = calcSeries(i, (int) counts[i]);
      ressLen[i] = counts[i];
    }

    for (int i = 8; i >= 0; i--) {
      ress[i] = merge(ress[i + 1], ressLen[i + 1], ress[i], ressLen[i]);
      ressLen[i] += ressLen[i + 1];
    }

    putLLArray(0, counts);
    putLLArray(0, ress);
    putLLArray(0, ressLen);
    message.Send(0);

//    System.out.println("counts " + Arrays.toString(counts));
//    System.out.println("ress " + Arrays.toString(ress));
//    System.out.println("ressLen " + Arrays.toString(ressLen));
  }

  void putLLArray(int target, long[] a) {
    message.PutInt(target, a.length);
    for (int i = 0; i < a.length; i++) {
      message.PutLL(target, a[i]);
    }
  }

  long[] getLLArray(int source) {
    int len = message.GetInt(source);
    long[] a = new long[len];
    for (int i = 0; i < len; i++) {
      a[i] = message.GetLL(source);
    }
    return a;
  }

  void server() {
    long totalRes = 0;
    long totalLen = 0;
    int maxDigit = 0;

    for (int i = nodeCount - 1; i >= 0; i--) {
      message.Receive(i);
      long[] counts = getLLArray(i);
      long[] ress = getLLArray(i);
      long[] ressLen = getLLArray(i);

      int newMaxDigit = maxDigit;
      for (int j = maxDigit + 1; j < 10; j++) {
        if (counts[j] != 0) {
          newMaxDigit = j;
        }
      }

//      totalRes = merge(totalRes, totalLen, ress[maxDigit], ressLen[maxDigit]);
      totalRes = merge(ress[maxDigit], ressLen[maxDigit], totalRes, totalLen);
      totalLen += ressLen[maxDigit];

      maxDigit = newMaxDigit;
    }

    long zeroCount = numberLength - totalLen;

    totalRes = mul(totalRes, pow(10, zeroCount));

    System.out.println(totalRes);
  }
}