Distributed Code Jam 2017 - Round1

B-large.cpp

#include<message.h>
#include<stdio.h>
#include "pancakes.h"

typedef long long ll;

#define MASTER_NODE 0

int main() {
  ll s = GetStackSize();
  ll d = GetNumDiners();
  ll nodes = NumberOfNodes();
  ll my_id = MyNodeId();

  ll unit_s = (s + nodes - 1) / nodes;
  ll start_s = unit_s * my_id;
  ll end_s = start_s + unit_s;
  if(s < end_s) end_s = s;

  ll pos = (0 < start_s && start_s < end_s ? GetStackItem(start_s-1) : 0);
  ll count = 0;
  for(ll i=start_s; i<end_s; ++i) {
    ll item = GetStackItem(i);
    if(item < pos) count++;
    pos = item;
  }
  PutLL(MASTER_NODE, count);
  Send(MASTER_NODE);

  if(my_id == MASTER_NODE) {
    ll ans = 1;
    for(int node=0; node<nodes; ++node) {
      Receive(node);
      ll result = GetLL(node);
      ans += result;
    }
    printf("%lld\n", ans);
  }
  return 0;
}

C-large.cpp

#include<message.h>
#include<stdio.h>
#include "weird_editor.h"

typedef long long ll;

#define MASTER_NODE 0

#define MOD 1000000007LL

ll fast_pow(ll x, ll n) {
  ll result = 1;
  while(n > 0) {
    if(n & 1) {
      result = (result * x) % MOD;
    }
    x = (x * x) % MOD;
    n >>= 1;
  }
  return result;
}

int main() {
  ll nodes = NumberOfNodes();
  ll my_id = MyNodeId();

  ll l = GetNumberLength();

  ll unit_l = (l + nodes - 1) / nodes;
  ll start_l = unit_l * my_id;
  ll end_l = start_l + unit_l;
  if(l < end_l) end_l = l;
  ll cur = 0;
  ll count[10];
  ll rev9 = fast_pow(9, MOD-2);
  for(ll i=0; i<10; ++i) count[i] = 0;
  for(ll i=end_l-1; start_l<=i; --i) {
    ll dig = GetDigit(i);
    if(cur < dig) cur = dig;
    if(cur == dig) ++count[cur];
  }
  for(ll i=0; i<10; ++i) {
    PutLL(MASTER_NODE, count[i]);
    Send(MASTER_NODE);
  }

  if(my_id == MASTER_NODE) {
    ll g_cur = 0;
    ll g_count[10];
    for(ll i=0; i<10; ++i) g_count[i] = 0;

    for(ll node=nodes-1; node>=0; --node) {
      for(ll i=0; i<10; ++i) {
        Receive(node);
        ll result = GetLL(node);
        if(result > 0) {
          if(g_cur < i) {
            g_cur = i;
          }
          if(g_cur == i) {
            g_count[i] += result;
          }
        }
      }
    }
    ll sum1 = 0;
    for(ll i=1; i<10; ++i) {
      sum1 += g_count[i];
    }
    ll g_index = l - sum1;
    ll ans = 0;
    for(ll i=1; i<10; ++i) {
      if(g_count[i] > 0) {
        ll krev9 = (i * rev9) % MOD;
        ll dd = (krev9 * (fast_pow(10, g_count[i]) + MOD - 1) % MOD) % MOD;
        dd = (dd * fast_pow(10, g_index)) % MOD;
        ans = (ans + dd) % MOD;
      }
      g_index += g_count[i];
    }
    printf("%lld\n", ans);
  }

  return 0;
}

D-small.cpp

#include<message.h>
#include<stdio.h>
#include "todd_and_steven.h"

typedef long long ll;

#define MASTER_NODE 0

#define MOD 1000000007LL

int main() {
  ll nodes = NumberOfNodes();
  ll my_id = MyNodeId();

  ll tl = GetToddLength();
  ll sl = GetStevenLength();

  if(my_id == MASTER_NODE) {
    ll left = 0, right = 0;
    ll count = 0;
    ll ans = 0;
    while(left < tl && right < sl) {
      ll lv = GetToddValue(left);
      ll rv = GetStevenValue(right);
      if(lv < rv) {
        ans = (ans + (lv ^ count)) % MOD;
        ++left;
      } else {
        ans = (ans + (rv ^ count)) % MOD;
        ++right;
      }
      ++count;
    }
    while(left < tl) {
      ll lv = GetToddValue(left);
      ans = (ans + (lv ^ count)) % MOD;
      ++left;
      ++count;
    }
    while(right < sl) {
      ll rv = GetStevenValue(right);
      ans = (ans + (rv ^ count)) % MOD;
      ++right;
      ++count;
    }
    printf("%lld\n", ans);
  }

  return 0;
}

E-small.cpp

#include<message.h>
#include<stdio.h>
#include "query_of_death.h"

typedef long long ll;

#define MASTER_NODE 0
#define CHILD_NODE 1

#define MOD 1000000007LL

int main() {
  ll nodes = NumberOfNodes();
  ll my_id = MyNodeId();

  ll l = GetLength();

  if(my_id == CHILD_NODE) {
    ll finish = 0;
    for(ll i=0; i<l && !finish; ++i) {
      ll first = 0;
      for(ll j=0; j<100; ++j) {
        ll v = GetValue(i);
        if(j == 0) first = v;
        if(first != v) {
          PutLL(MASTER_NODE, i);
          Send(MASTER_NODE);
          PutLL(MASTER_NODE, first);
          Send(MASTER_NODE);
          finish = 1;
        }
      }
    }
  }

  if(my_id == MASTER_NODE) {
    Receive(CHILD_NODE);
    ll broken_i = GetLL(CHILD_NODE);
    Receive(CHILD_NODE);
    ll value = GetLL(CHILD_NODE);
    ll ans = 0;
    for(ll i=0; i<l; ++i) {
      if(i == broken_i) {
        ans += value;
      } else {
        ll v = GetValue(i);
        ans += v;
      }
    }
    printf("%lld\n", ans);
  }

  return 0;
}