Submission #310688

#	Time	Username	Problem	Language	Result	Execution time	Memory
310688		spatarel	Devil's Share (RMI19_devil)	C++17	100 / 100	440 ms	2968 KiB

devil

#include <bits/stdc++.h>

using namespace std;

using Test = pair <vector <int>, int>; // (freq, K)

void ReadTest(Test &t) {
    int& K = t.second;
    cin >> K;
    vector <int>& v = t.first;
    v.resize(10);
    for (int i = 1; i < 10; ++i) {
        cin >> v[i];
    }
}

namespace CataFrancu {

#define NIL -1

struct list {
  int next;      /* index of the next digit in this chain */
  int end;       /* index of the last digit in this chain */
  char digit;    /* 0-9 */
  char distinct; /* this list is different from the one to its left */
};

/* print lists in the [from, to) range, limited to max digits */
void print_lists(stringstream &ss, const vector<list>& l, const vector<int>& counts, int from, int to, int max) {
  for (int i = from; i < to; i++) {
    int pos = i;
    while (pos != NIL) {
      if (max) {
        ss << (char)('0' + l[pos].digit);
        max--;
      }
      pos = l[pos].next;
    }
  }
}

string Solve(Test t) {
  vector <int>& counts = t.first;
  int& k = t.second;

  int n = 0, c, i, j;
  for (int i = 1; i < 10; ++i) {
    n += counts[i];
  }

  vector <list> l(n);

  /* initialize N single-digit chains */
  c = 0;
  for (i = 0; i < n; i++) {
    while (!counts[c]) {
      c++;
    }
    l[i].next = NIL;
    l[i].end = i;
    l[i].digit = c;
    l[i].distinct = (!i || (l[i].digit != l[i - 1].digit));
    counts[c]--;
  }

  /* starting index of the rightmost run of identical chains */
  /* (we know the ending index is n - k) */
  int jstart = n - k;
  while (jstart && (l[jstart - 1].digit == l[n - k].digit)) {
    jstart--;
  }

  /* Distribute lists, starting from the left, in round robin fashion, into
     the run of identical chains to the right. In time, the run will shrink
     towards the right. Stop when there are no more elements to distribute to
     the left of the run. */
  i = 0;        /* list currently being distributed */
  j = jstart;   /* list currently being appended to */
  while (i < jstart || j > jstart) { /* stop when i, j and jstart coincide */
    /* append l[i] to l[j] */
    l[l[j].end].next = i;
    l[j].end = l[i].end;

    /* shrink the run if l[i] is distinct from the one before it */
    if (l[i].distinct) {
      l[j].distinct = 1;
      jstart = j;
    }

    i++;
    j++;
    if (j > n - k) {
      j = jstart;
    }
  }

  /* the devil's due is the chain at position n - k, possibly padded to
     length k with larger digits */
  stringstream ss;
  //print_lists(ss, l, counts, n - k, n, k);  /* print the devil's due */
  print_lists(ss, l, counts, jstart, n, n); /* print the complete permutation */
  return ss.str();
}

void SolveCataFrancu() {
    int T;
    cin >> T;
    while (T--) {
        Test t;
        ReadTest(t);
        cout << Solve(t) << '\n';
    }
}

}

int main() {
  CataFrancu::SolveCataFrancu();
  return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 29 / 29
• Subtask 4: 44 / 44