제출 #718564

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

perm

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

using namespace std;

const long long MX = 1e18;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int randint(int l, int r){
	return uniform_int_distribution <int> (l, r) (rng);
}

double randdouble(double l, double r){
	return uniform_real_distribution <double> (l, r) (rng);
}

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;
}

vector <int> try_opt(long long k, int sz){
	vector <int> ans;
	for(int i = 0; i < sz - 1; ++i){
		vector <int> tmp;
		int sz = i + 1;
		if (ans.empty()) ans.push_back(i);
		else {
			int l = -1, r = sz;
			while(l + 1 < r){
				int p = (l + r) >> 1;
				vector<int> cur = ans;
				cur.insert(cur.begin() + p, i);
				int v = count_increasing(cur);
				if (v == k) return cur;
				if (v <= k) l = p;
				else r = p;
			}

			int ran = randint(1, 30);
			if (ran <= 29) ran = 0;
			else ran = 1;
			l -= min(ran, l);

			ans.insert(ans.begin() + l, i);
		}

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

	return {-1};
}

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 {
			int l = -1, r = sz;
			while(l + 1 < r){
				int p = (l + r) >> 1;
				vector<int> cur = ans;
				cur.insert(cur.begin() + p, i);
				if (count_increasing(cur) <= k) l = p;
				else r = p;
			}
			ans.insert(ans.begin() + l, i);
		}

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

	while (1.0 * clock() / CLOCKS_PER_SEC <= 0.6){
		vector <int> ans1 = try_opt(k, ans.size());
		if (ans1.back() == -1) continue;
		if (ans1.size() < ans.size()) ans = ans1;
	}

	return ans;
}

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