Submission #1061207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061207		Muhammet	Permutation (APIO22_perm)	C++17	71.22 / 100	739 ms	1372 KiB

perm

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

using namespace std;

#define ll long long
#define sz(s) (int)s.size()

const ll M = 1e18+1;

ll f(vector <int> v){
    int n = sz(v);
    vector <ll> dp(n,1);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            if(v[j] < v[i]){
            	if(M-dp[j] < dp[i]) return M;
            	dp[i] += dp[j];
            }
        }
    }

    ll k = 0;
    for(int i = 0; i < n; i++){
    	if(M-dp[i] < k) return M;
        k += dp[i];
    }
    return k+1;
}

vector<int> construct_permutation(ll k){
	int x = -1;
	vector <int> v;
	int t = 1000;
	bool tr1 = 0;
	while(t--){
		x++;
		v.push_back(x);
		ll y = f(v);
		if(y == k){
			tr1 = 1;
			break;
		}
		if(y <= k) continue;
		for(int i = sz(v)-2; i >= 0; i--){
			swap(v[i],v[i+1]);
			y = f(v);
			if(y <= k) break;
		}
		if(y == k){
			tr1 = 1;
			break;
		}
	}
	x = -1;
	vector <int> v3 = v;
	deque <int> v2;
	bool tr = 1;
	while(k > 0){
		vector <int> v1;
		ll k1 = 2;
		x++;
		v1.push_back(x);
		while((k1-1+tr) < k){
			if(k/2 < (k1-1+tr)) break;
			x++;
			v1.push_back(x);
			k1 *= 2;
		}
		if(k1-1+tr > k){
			k1 /= 2;
			v1.pop_back();
			x--;
		}
		k -= (k1-1+tr);
		for(int i = sz(v1)-1; i >= 0; i--){
			v2.push_front(v1[i]);
		}
		tr = 0;
	}
	v.clear();
	for(int i = 0; i < sz(v2); i++){
		v.push_back(v2[i]);
	}
	if(f(v3) == k){
		return v3;
	}
	else {
		return v;
	}
}

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:35:7: warning: variable 'tr1' set but not used [-Wunused-but-set-variable]
   35 |  bool tr1 = 0;
      |       ^~~

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