Submission #1178006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178006		Halym2007	Permutation (APIO22_perm)	C++17	91.33 / 100	2 ms	328 KiB

perm

#include <bits/stdc++.h>
#include "perm.h"
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 2e5 + 5;

//
//static long long MX = 1e18;
//
//static bool check_permutation(vector<int> v)
//{
//	sort(v.begin(),v.end());
//	for(int i=0;i<v.size();i++)
//		if(v[i]!=i) return 0;
//	return 1;
//}
//
//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> construct_permutation(ll k) {
	int tt = 0;
	vector <int> ret;
	for (ll i = 59; i >= 0; i--) {
		if (k >> i & 1) {
			if (!tt) {
				tt = 1;
				int san = 1;
				for (int j = 1; j <= i; ++j) {
					ret.pb (san);
					san += 100;
				} 
			}
			else {
				ret.pb (ret[i] - 1);
			}
		}
	}
	map <int, int> m;
	for (int i : ret) {
		m[i] = 1;
	}
	int bel = 0;
	for (auto i : m) {
		m[i.ff] = bel++;
	}
	for (int &i : ret) {
		i = m[i];
	}
	assert ((int)ret.sz <= 117);
	return ret;
}


//int main() {
//	freopen ("input.txt", "r", stdin);
//	int t;
//	assert(1 == scanf("%d", &t));
//	while(t--)
//	{
//		long long k;
//		assert(1 == scanf("%lld",&k));
//		vector<int> ret=construct_permutation(k);
//		if(!check_permutation(ret))
//		{
//			printf("WA: Returned array is not a permutation\n");
//			exit(0);
//		}
//		long long inc=count_increasing(ret);
//		if(inc!=k) {
//			if(inc==MX+1)
//				printf("WA: Expected %lld increasing subsequences, found more than %lld\n",k, MX);
//			else
//				printf("WA: Expected %lld increasing subsequences, found %lld\n",k,inc);
//			exit(0); 
//		}
//		printf("%d\n",(int)ret.size());
//		for(int i=0;i<ret.size();i++)
//		{
//			printf("%d",ret[i]);
//			if(i+1==ret.size())
//				printf("\n");
//			else
//				printf(" ");
//		}
//	}
//	return 0;
//}

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