oj.uz

Submission #593774

# Submission time Handle Problem Language Result Execution time Memory
593774 2022-07-11T15:08:29 Z CSQ31 Permutation (APIO22_perm) C++17
100 / 100
 2 ms 340 KB 
#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define INF (int)(1e9+1)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
vector<int> construct_permutation(ll k)
{
	vector<int>v;
	while(k){
		v.pb(k%4);
		k/=4;
	}
	reverse(all(v));
	deque<int>ans;
	//4x//[N] n+1 n+2 
	//4x+1//n+3 [N] n+1 n+2
	//4x+2//n+2 [N] n+1 n+3
	//[N] n+1 n+2 1.5
	//for(int x:v)cout<<x<<" ";
	//cout<<'\n';
	if(v[0] == 2)ans.pb(0);
	if(v[0] == 3){
		ans.pb(1);
		ans.pb(0);
	}
	for(int i=1;i<sz(v);i++){
		if(!v[i]){
			ans.pb(sz(ans));
			ans.pb(sz(ans));	
		}
		else if(v[i] == 1){
			ans.pb(sz(ans));
			ans.pb(sz(ans));
			ans.push_front(sz(ans));	
		}else if(v[i] ==2){
			ans.pb(sz(ans));
			ans.push_front(sz(ans));
			ans.pb(sz(ans));	
		}else{
			bool a = 0,ok = 0;
			for(int x:ans){
				if(x==1)a=1;
				if(x==0 && a)ok = 1;
			}
			if(ok){
				ans.pb(sz(ans));
				ans.pb(sz(ans));
				for(int &x:ans)if(x>1)x++;
				ans.pb(2);
			}else{
				ans.pb(sz(ans));
				ans.pb(-1);
				ans.pb(sz(ans)-1);
				ans.pb(-2);
				for(int &x:ans)x+=2;
				
			}
		}
	}
	//for(int x:ans)cout<<x<<" ";
	//cout<<'\n';
	vector<int>res;
	for(int x:ans)res.pb(x);
	//for(int x:ans)cout<<x<<" ";
	//cout<<'\n';
	return res;
}

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 212 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 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 1 ms 296 KB Output is correct
7 Correct 2 ms 340 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 300 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct