Submission #718554

#	Time	Username	Problem	Language	Result	Execution time	Memory
718554		vjudge1	Permutation (APIO22_perm)	C++17	91.33 / 100	169 ms	448 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;
}
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;
		for(int i = 0; i < (int)ans.size() - 1; ++i){
			vector <int> tmp;
			int sz = i + 1;
			if (ans1.empty()) ans1.push_back(i);
			else {
				int bound = 0;
				for(int p = 0; p < sz; ++p){
					vector<int> cur = ans1;
					cur.insert(cur.begin() + p, i);
					if (count_increasing(cur) <= k) tmp = cur, bound = p;
					else break;
				}

				int r = randint(0, 2);
				bound = max(0, bound - r);

				ans1.insert(ans1.begin() + bound, i);
				
				ans1 = tmp;
			}

			if (count_increasing(ans1) == k){
				ans = ans1;
				break;
			}
		}
	}*/

	return ans;
}

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