제출 #625050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
625050		MilosMilutinovic	순열 (APIO22_perm)	C++17	10 / 100	1096 ms	340 KiB

perm

#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 / 10
• Subtask 2: 0 / 90