oj.uz

Submission #625050

# Submission time Handle Problem Language Result Execution time Memory
625050 2022-08-09T09:33:44 Z MilosMilutinovic Permutation (APIO22_perm) C++17
10 / 100
 1000 ms 340 KB 
#include "perm.h"
#include <bits/stdc++.h>

using namespace std;

long long Count(vector<int> p) {
  int n = p.size();
  vector<long long> dp(n);
  for (int i = 0; i < n; i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j++) {
      if (p[j] < p[i]) {
        dp[i] += dp[j];
      }
    }
  }       
  long long cnt = 1;
  for (int i = 0; i < n; i++) {
    cnt += dp[i];
  }
  return cnt;
}

vector<int> construct_permutation(long long k) {
  if (k <= 90) {
    vector<int> ans;
    for (int i = k - 2; i >= 0; i--) {
      ans.push_back(i);
    }
    return ans;
  }
  for (int len = 50; len >= 1; len--) {
    vector<int> perm(len);
    for (int i = 0; i < len; i++) {
      perm[i] = i;
    }   
    if (Count(perm) < k) {
      continue;
    }
    reverse(perm.begin(), perm.end());
    long long total = Count(perm);
    do {
      vector<tuple<long long, int, int>> c;
      for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
          swap(perm[i], perm[j]);
          c.emplace_back(Count(perm) - total, i, j);                    
          swap(perm[i], perm[j]);
        }
      }   
      sort(c.begin(), c.end());
      tuple<long long, int, int> f = make_tuple(-1, -1, -1);
      for (auto& p : c) {
        if (get<0>(p) > 0 && total + get<0>(p) <= k) {
          f = p;          
        }
      }
      if (get<0>(f) == -1) {
        break;
      }
      total += get<0>(f);
      swap(perm[get<1>(f)], perm[get<2>(f)]);
    } while (total < k);
    if (total == k) {
      return perm;
    }
  }
  return vector<int>(1, 0);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
0.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Execution timed out 1096 ms 340 KB Time limit exceeded
4 Halted 0 ms 0 KB -