제출 #718420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
718420		vjudge1	순열 (APIO22_perm)	C++17	91.33 / 100	672 ms	452 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>

using namespace std;

const long long MX = 1e18;

long long count_increasing(const vector<int>& v) {
  vector<long long> dp(v.size() + 1, 0);
  dp[0] = 1;
  for (int x : v)
  {
  	for (int i = 0; i <= x; i++)
  	{
  		dp[x+1] += dp[i];
  		dp[x+1] = min(dp[x+1],MX+1);
  	}
  }
  long long result = 0;
  for (int i = 0; i <= (int)v.size(); i++){
  	result += dp[i];
  	result = min(result,MX+1);
  }
  return result;
}
std::vector<int> construct_permutation(long long k)
{
	vector <int> ans;
	//return ans;
	for(int i = 0;; ++i){
		vector <int> tmp;
		int sz = i + 1;
		if (ans.empty()) ans.push_back(i);
		else {
			for(int p = 0; p < sz; ++p){
				vector<int> cur = ans;
				cur.insert(cur.begin() + p, i);
				if (count_increasing(cur) <= k) tmp = cur;
				else break;
			}
			ans = tmp;
		}

		if (count_increasing(ans) == k){
			break;
		}
	}

	return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 81.333333333 / 90