oj.uz

답안 #310688

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
310688 2020-10-07T16:05:03 Z spatarel Devil's Share (RMI19_devil) C++17
100 / 100
 440 ms 2968 KB 
#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.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 1272 KB Output is correct
2 Correct 191 ms 1784 KB Output is correct
3 Correct 163 ms 1784 KB Output is correct
4 Correct 294 ms 2168 KB Output is correct
5 Correct 42 ms 1400 KB Output is correct
6 Correct 43 ms 1272 KB Output is correct
7 Correct 43 ms 1272 KB Output is correct
8 Correct 39 ms 1448 KB Output is correct
9 Correct 37 ms 2836 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 201 ms 1272 KB Output is correct
2 Correct 101 ms 1528 KB Output is correct
3 Correct 38 ms 2796 KB Output is correct
4 Correct 43 ms 2936 KB Output is correct
5 Correct 50 ms 2968 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 384 KB Output is correct
2 Correct 261 ms 1272 KB Output is correct
3 Correct 191 ms 1784 KB Output is correct
4 Correct 163 ms 1784 KB Output is correct
5 Correct 294 ms 2168 KB Output is correct
6 Correct 42 ms 1400 KB Output is correct
7 Correct 43 ms 1272 KB Output is correct
8 Correct 43 ms 1272 KB Output is correct
9 Correct 39 ms 1448 KB Output is correct
10 Correct 37 ms 2836 KB Output is correct
11 Correct 201 ms 1272 KB Output is correct
12 Correct 101 ms 1528 KB Output is correct
13 Correct 38 ms 2796 KB Output is correct
14 Correct 43 ms 2936 KB Output is correct
15 Correct 50 ms 2968 KB Output is correct
16 Correct 323 ms 2040 KB Output is correct
17 Correct 315 ms 2168 KB Output is correct
18 Correct 254 ms 1912 KB Output is correct
19 Correct 440 ms 2680 KB Output is correct
20 Correct 41 ms 1272 KB Output is correct
21 Correct 44 ms 1400 KB Output is correct
22 Correct 36 ms 1456 KB Output is correct
23 Correct 41 ms 2800 KB Output is correct