Submission #786618

#	Time	Username	Problem	Language	Result	Execution time	Memory
786618		mindiyak	Permutation (APIO22_perm)	C++17	10 / 100	4 ms	596 KiB

perm

#include "perm.h"
#include <cmath>
#include <deque>
#include <iostream>
#include <algorithm>
#define ll long long
#define pb push_back
using namespace std;


std::vector<int> construct_permutation(long long k)
{
	if(k == 0){
		return vector<int>(0);
	}k--;
	vector<ll> powers;
	for(int i=0;i<63;i++){
	// for(int i=0;i<10;i++){
		powers.pb(pow(2,i)-1);
		// cout << i << " " << powers[i] << endl;
	}
	deque<pair<int,int>> arr;
	int n=0;
	while(k > 0){
		int length = upper_bound(powers.begin(),powers.end(),k) - powers.begin();
		if(length != 0){
			length --;
		}
		arr.push_front({n,n+length});
		// cout << k << " " << n << " to " << n + length << " " << pow(2,length)-1 <<endl;
		n += length;
		k -= pow(2,length)-1;
	}
	vector<int> ans;
	for(int i=0;i<arr.size();i++){
		for(int j=arr[i].first;j<arr[i].second;j++){
			ans.pb(j);
			// cout << j << " ";
		}
	}
	// cout << endl;
	return ans;
}

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:35:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i=0;i<arr.size();i++){
      |              ~^~~~~~~~~~~

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