fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int numTest;
  6. int n, k;
  7. long long x;
  8. vector<int> s;
  9.  
  10. void subtask4() {
  11.     int maxCount = 1;
  12.     for (int i = 2; i <= k; i++) {
  13.         maxCount *= i;
  14.     }
  15.     if (x > maxCount) {
  16.         cout << "-1\n";
  17.         return;
  18.     }
  19.     vector<int> dif(n + 1), c(n + 1);
  20.     for (int i = 1; i + k <= n; i++) {
  21.         if (abs(c[i]) >= n) {
  22.             cout << "-1\n";
  23.             return;
  24.         }
  25.         dif[i] = s[i + 1] - s[i];
  26.         c[i + k] = c[i] + dif[i];
  27.     }
  28.     vector<int> order(k);
  29.     iota(order.begin(), order.end(), 1);
  30.     vector<vector<int>> candidates;
  31.     do {
  32.         vector<bool> mark(n + 1, false);
  33.         vector<int> p(n + 1);
  34.         auto valid = [&](int v) {
  35.             bool res = 1 <= v && v <= n && !mark[v];
  36.             mark[v] = true;
  37.             return res;
  38.         };
  39.         int minVal = 1;
  40.         bool failed = false;
  41.         for (int j = 0; j < k and !failed; j++) {
  42.             int sta = order[j];
  43.             while (mark[minVal]) {
  44.                 ++minVal;
  45.             }
  46.             int minC = 2 * n;
  47.             for (int i = sta; i <= n; i += k) {
  48.                 minC = min(minC, c[i]);
  49.             }
  50.             p[sta] = minVal - minC;
  51.             if (!valid(p[sta])) {
  52.                 failed = true;
  53.             }
  54.             for (int i = sta + k; i <= n; i += k) {
  55.                 p[i] = p[sta] + c[i];
  56.                 if (!valid(p[i])) {
  57.                     failed = true;
  58.                     break;
  59.                 }
  60.             }
  61.         }
  62.         int s1 = 0;
  63.         for (int i = 1; i <= k; i++) {
  64.             s1 += p[i];
  65.         }
  66.         if (s1 != s[1]) {
  67.             failed = true;
  68.         }
  69.         if (!failed) {
  70.             candidates.push_back(vector<int>(p.begin(), p.begin() + k + 1));
  71.         }
  72.     } while (next_permutation(order.begin(), order.end()));
  73.     sort(candidates.begin(), candidates.end());
  74.     if (x > candidates.size()) {
  75.         cout << "-1\n";
  76.         return;
  77.     }
  78.     auto p = candidates[x - 1];
  79.     p.resize(n + 1);
  80.     for (int i = 1; i <= n; i++) {
  81.         if (i > k) {
  82.             p[i] = p[i - k] + dif[i - k];
  83.         }
  84.         cout << p[i] << ' ';
  85.     }
  86.     cout << '\n';
  87. }
  88.  
  89. int main() {
  90.     ios_base::sync_with_stdio(0);
  91.     cin.tie(0);
  92.     cout.tie(0);
  93.  
  94.     freopen("COMPRESS.inp", "r", stdin);
  95.     freopen("COMPRESS.out", "w", stdout);
  96.  
  97.     cin >> numTest;
  98.     while (numTest-- > 0) {
  99.         cin >> n >> k >> x;
  100.         s.resize(n - k + 1 + 1);
  101.         for (int i = 1; i <= n - k + 1; i++) {
  102.             cin >> s[i];
  103.         }
  104.         subtask4();
  105.     }
  106.  
  107.     return 0;
  108. }
  109.  
  110.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QANHNc
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!