Submission #638734

#	Time	Username	Problem	Language	Result	Execution time	Memory
638734		minhcool	Permutation (APIO22_perm)	C++17	100 / 100	257 ms	2896 KiB

perm

#include<bits/stdc++.h>
using namespace std;
 
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int a[11], answer[N];
 
vector<int> save[N];
 
int cal(vector<int> v){
	int ans = 0;
	for(int i = 0; i < (1LL << v.size()); i++){
		vector<int> v2;
		bool ok = 1;
		for(int j = 0; j < v.size(); j++){
			if(i & (1LL << j)) v2.pb(v[j]);
		}
		for(int j = 1; j < v2.size(); j++) ok &= (v2[j] > v2[j - 1]);
		ans += ok;
	}
	return ans;
}
 
vector<int> construct_permutation(ll k){
	for(int i = 1; i <= 6; i++) a[i] = i;
	do{
		int pos1, pos2;
		for(int i = 1; i <= 6; i++){
			if(a[i] == 1) pos1 = i;
			if(a[i] == 2) pos2 = i;
		}
		if(pos1 < pos2) continue;
		vector<int> x;
		for(int i = 1; i <= 6; i++) x.pb(a[i]);
		save[cal(x)] = x;
	}while(next_permutation(a + 1, a + 7));
	//for(auto it : save[10]) cout << it << " ";
	//cout << "\n";
	if(k <= 8){
		vector<int> temp;
		for(int i = k - 2; i >= 0; i--) temp.pb(i);
		return temp;
	}
	vector<int> bits;
	while(k){
		bits.pb(k % 2);
		k /= 2;
	}
	reverse(bits.begin(), bits.end());
	assert(bits[0] == 1);
	//cout << bits[0] * 8 + bits[1] * 4 + bits[2] * 2 + bits[3] << "\n";
	//exit(0);
	for(int i = 1; i <= 6; i++) answer[i] = save[bits[0] * 8 + bits[1] * 4 + bits[2] * 2 + bits[3]][i - 1];
	int cnt = 6;
	for(int i = 4; i < bits.size(); i += 2){
		if(i == bits.size() - 1){
			cnt++;
			answer[cnt] = cnt;
			if(bits[i] == 1){
				for(int j = 1; j <= cnt; j++) answer[j]++;
				cnt++;
				answer[cnt] = 1;
			}
			break;
		}
		cnt++;
		answer[cnt] = cnt;
		cnt++;
		answer[cnt] = cnt;
		int tempo = bits[i] * 2 + bits[i + 1];
		if(!tempo) continue;
		vector<int> x;
		for(int j = 1; j <= cnt; j++) x.pb(answer[j]);
		//cout << cal(x) << "\n";
		if(tempo == 1){
			//cout << "OK1\n";
			for(int j = 1; j <= cnt; j++) answer[j]++;
			cnt++;
			answer[cnt] = 1;
		}	
		else if(tempo == 2){
			//cout << "OK2\n";
			for(int j = cnt; j >= 1; j--) answer[j + 1] = answer[j];
			cnt++;
			for(int j = 2; j <= cnt; j++) if(answer[j] == (cnt - 1)) answer[j]++;
			answer[1] = cnt - 1;
		}
		else{
			//cout << "OK3\n";
			//int pos1, pos2;
			for(int j = 1; j <= cnt; j++) if(answer[j] > 2) answer[j]++;
			cnt++;
			answer[cnt] = 3;
		}
		x.clear();
		for(int j = 1; j <= cnt; j++) x.pb(answer[j]);
		int pos1, pos2;
		//cout << cal(x) << "\n";
		for(int j = 1; j <= cnt; j++){
			if(answer[j] == 1) pos1 = j;
			if(answer[j] == 2) pos2 = j;
		}
		//cout << "P " << pos1 << " " << pos2 << "\n";
	}
	vector<int> a;
	for(int i = 1; i <= cnt; i++) a.pb(answer[i] - 1);
	return a;
}
 
//int n, a[N];
 
/*
void process(){
	int q;
	cin >> q;
	while(q--){
		int x;
		cin >> x;
		vector<int> temp = construct_permutation(x);
		cout << cal(temp) << "\n";
		for(auto it : temp) cout << it << " ";
		cout << "\n";
	}
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	process();
}*/

Compilation message (stderr)

perm.cpp:19:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   19 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
perm.cpp: In function 'int cal(std::vector<int>)':
perm.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int j = 0; j < v.size(); j++){
      |                  ~~^~~~~~~~~~
perm.cpp:33:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int j = 1; j < v2.size(); j++) ok &= (v2[j] > v2[j - 1]);
      |                  ~~^~~~~~~~~~~
perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i = 4; i < bits.size(); i += 2){
      |                 ~~^~~~~~~~~~~~~
perm.cpp:71:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   if(i == bits.size() - 1){
      |      ~~^~~~~~~~~~~~~~~~~~
perm.cpp:112:7: warning: variable 'pos1' set but not used [-Wunused-but-set-variable]
  112 |   int pos1, pos2;
      |       ^~~~
perm.cpp:112:13: warning: variable 'pos2' set but not used [-Wunused-but-set-variable]
  112 |   int pos1, pos2;
      |             ^~~~
perm.cpp:47:3: warning: 'pos2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |   if(pos1 < pos2) continue;
      |   ^~

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