oj.uz

Submission #580266

# Submission time Handle Problem Language Result Execution time Memory
580266 2022-06-20T23:26:58 Z angelo_torres Permutation (APIO22_perm) C++17
100 / 100
 2 ms 352 KB 
#include <bits/stdc++.h>
#define f(i,j,n) for(ll i = j; i < n; ++i)
#define fr(i,j,n) for(ll i = j; i >= n; --i)
#define sz(v) (ll) v.size()

using namespace std;
typedef long long ll;
typedef vector<int> vi; 
typedef vector<ll> vll;

const int N = 4e3 + 20;
const ll mod = 1e9 + 7;

vi construct_permutation(ll k){
	ll aux = k, cn = 0;
	vll in[5];
	ll np[5];
	in[1] = {}, in[2] = {0}, in[3] = {1,0}; 
	np[1] = -1, np[2] = 0, np[3] = 1;
	while(aux >= 4) aux >>= 2, cn++;
	vll ans = in[aux];
	ll na = np[aux];
	fr(i,cn,1){
		ll j = (k>>(2*(i-1)))%4;
		if(j == 0){
			ans.push_back(++na);
			ans.push_back(++na);
		}
		if(j == 1){
			ans.push_back(++na);
			ans.push_back(++na);
			for(auto &it : ans) it++;
			ans.push_back(0);
			na++;
		}
		if(j == 2){
			ans.push_back(++na);
			for(auto &it : ans) it++;
			ans.push_back(0);
			na++;
			ans.push_back(++na);
		}
		if(j == 3){
			ll p[2];
			f(ji,0,sz(ans)) if(ans[ji] < 2) p[ans[ji]] = ji;
			if(p[1] < p[0]){
				ans.push_back(++na);
				ans.push_back(++na);
				for(auto &it : ans) if(it >= 2) it++;
				ans.push_back(2);
				na++;
			}
			else{
				ans.push_back(++na);
				for(auto &it : ans) it++;
				ans.push_back(0);
				na++;
				ans.push_back(++na);
				for(auto &it : ans) it++;
				ans.push_back(0);
				na++;
			}
		}
	}
	vi ai;
	for(auto it : ans) ai.push_back((int) it);
	return ai;
}


// int main(){
// 	int k; cin >> k;
// 	vector<int> nm = construct_permutation(k);
// 	for(auto it : nm) cout << it << " ";
// 	cout << endl;
// 	return 0;
// }

Subtask #1
10.0 / 10.0

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

Subtask #2
90.0 / 90.0

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