oj.uz

Submission #594650

# Submission time Handle Problem Language Result Execution time Memory
594650 2022-07-12T19:05:53 Z mohammad_kilani Permutation (APIO22_perm) C++17
100 / 100
 2 ms 340 KB 
#include "perm.h"
#include <bits/stdc++.h>
using namespace std;


std::vector<int> construct_permutation(long long k){
	vector< int > ret;
	int mx = 0;
	while((1LL << (mx + 1)) <= k)
		mx++;
	int a = 0;
	for(int i = 0 ;i <= mx;i++){
		if(((k >> i) & 1) == 1)
			a++;
	}
	
	if(a <= 30){
		for(int i = 0 ;i < mx;i++)
			ret.push_back(i);
		k -= (1LL << mx);
		for(int i = mx - 1 ;i >= 0;i--){
			if(((k >> i) & 1) == 1)
				ret.insert(ret.begin() + i , (int)ret.size());
		}
		return ret;
	}
	

	vector< int > v;

	k -= (1LL << mx);

	int counter = 0;

	for(int a , b , i = 0 ;i < mx - 2;i++){
		a = ((k >> i) & 1);
		b = ((k >> (i + 1)) & 1);
		if(a == 0 || b == 0){
			ret.push_back(counter++);
			continue;
		}
		k -= (1LL << i);
		k -= (1LL << (i + 1));
		v.push_back(counter++);
		ret.push_back(counter++);
	}


	v.insert(v.begin() , counter + 1);
	v.insert(v.begin() , counter);
	counter+=2;

	ret.push_back(counter++);
	
	for(int i = mx - 1 ;i >= 0;i--){
		if(((k >> i) & 1) == 1)
			ret.insert(ret.begin() + i , counter++);
	}


	while((int)v.size() > 0){
		ret.push_back(v.back());
		v.pop_back();
	}

	return ret;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 292 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 296 KB Output is correct
11 Correct 2 ms 296 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct