Submission #1139612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139612		JelalTkm	Permutation Recovery (info1cup17_permutation)	C++20	0 / 100	1 ms	1088 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 1e4 + 100;
const int md = 1e9 + 7;
const int INF = 1e9;

struct segtree {
 
  vector<int> tree;
  int size;
 
  void init(int n) {
    size = 1;
    while (size < n) size <<= 1;
    tree.assign(2 * size - 1, 0);
  }
 
  void build(int n, int x, int lx, int rx) {
    if (rx - lx == 1) {
      if (lx < n) {
        tree[x] = 1;
      }
    } else {
      int m = (lx + rx) >> 1;
      build(n, 2 * x + 1, lx, m);
      build(n, 2 * x + 2, m, rx);
      tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
    }
  }
 
  void build(int n) {
    init(n);
    build(n, 0, 0, size);
  }
 
  void set(int i, int v, int x, int lx, int rx) {
    if (rx - lx == 1) {
      tree[x] = v;
      return;
    }
    int m = (lx + rx) >> 1;
    if (i < m) {
      set(i, v, 2 * x + 1, lx, m);
    } else {
      set(i, v, 2 * x + 2, m, rx);
    }
    tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
  }
 
  void set(int i, int v) {
    set(i, v, 0, 0, size);
  }
 
  int find_k(int k, int x, int lx, int rx) {
    if (tree[x] < k)
      return 0;
    if (rx - lx == 1)
      return lx;
    else {
      int m = (lx + rx) >> 1;
      if (tree[2 * x + 1] >= k)
        return find_k(k, 2 * x + 1, lx, m);
      else {
        k -= tree[2 * x + 1];
        return find_k(k, 2 * x + 2, m, rx);
      }
    }
  }
 
  int find_k(int k) {
    return find_k(k, 0, 0, size);
  }

};

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T = 1;
  // cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<int> b(n);
    for (int i = 0; i < n; i++)
      cin >> b[i];

    vector<int> a(n);
    a[0] = b[0];
    for (int i = 1; i < n; i++)
      a[i] = b[i] - b[i - 1];

    vector<vector<int>> dp(n + 1, vector<int> (N, INF));
    b[0] = 0;
    dp[0][a[0]] = min(dp[0][a[0]], 1ll);
    dp[0][0] = min(dp[0][0], 0ll);
    for (int i = 1; i < n; i++) {
      dp[i][a[i]] = min(dp[i][a[i]], 1ll);
      b[i] = dp[i - 1][a[i] - 1];
      for (int j = 0; j < N; j++) {
        dp[i][j] = min(dp[i - 1][j], dp[i][j]);
        if (j + a[i] < N && dp[i - 1][j] != INF)
          dp[i][j + a[i]] = min(dp[i][j + a[i]], dp[i - 1][j] + 1);
      }
    }

    segtree st;
    st.build(n);
 
    vector<int> ans;
    for (int i = n - 1; i >= 0; i--) {
      int x = st.find_k(b[i] + 1);
      ans.push_back(x + 1);
      st.set(x, 0);
    }
 
    reverse(ans.begin(), ans.end());
    for (int i = 0; i < n; i++)
      cout << ans[i] << " ";
    cout << '\n';
  }
  return 0;
}
// 1 6 3 4 2 5
// 1 2 2 4 2 10

// 0 1 1 2 1 4
// 1 6 3 4 2 5

• Subtask 1: 0 / 100