Submission #1077513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077513		Halym2007	Permutation (APIO22_perm)	C++17	100 / 100	3 ms	600 KiB

perm

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
const int N = 2e5 + 5;

vector <int> construct_permutation(ll k) {
	string s;
	ll oo = k;
	while (oo > 0) {
		s += char ((oo % 4) + 48);
		oo /= 4;
	}
	reverse(s.begin(), s.end());
	vector <double> ret;
	bool ok = 0;
	int mn = 0, mx = 0;
	if (s[0] == '2') {
		ret.pb (0);
	}
	else if (s[0] == '3') {
		ret.pb (1);
		ret.pb (0);
		ok = 1;
		mx = 1;
	}
	
	for (int i = 1; i < (int)s.sz; ++i) {
		if (s[i] == '0' or s[i] == '1') {
			ret.pb (mx + 1);
			ret.pb (mx + 2);
			if (s[i] == '1') {
				ret.pb (mn - 1);
				mn--;
			}
			mx += 2;
		}
		else if (s[i] == '2') {
			ret.pb (mx + 1);
			ret.pb (mn - 1);
			ret.pb (mx + 2);
			mn--;
			mx += 2;
		}
		else {
			if (ok) {
				ret.pb (mx + 1);
				ret.pb (mx + 2);
				ret.pb ((mn + 1) + 0.5);
			}
			else {
				ret.pb (mx + 1);
				ret.pb (mn - 1);
				ret.pb (mx + 2);
				ret.pb (mn - 2);
				ok = 1;
				mn -= 2;
			}
			mx += 2;
		}
	}	
	map <double, int> m;
	for (double i : ret) {
		m[i]++;
	}
	int sum = 0;
	for (auto i : m) {
		m[i.ff] = sum + i.ss - 1;
		sum += i.ss;
	}
	vector <int> jog;
	for (double i : ret) {
		jog.pb (m[i]);
		m[i]--;
	}
	return jog;
}

//int main () {
//	freopen ("input.txt", "r", stdin);
//	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//	int q;
//	cin >> q;
//	while ( q-- ) {
//		ll k;
//		cin >> k;
//		vector <int> kk = construct_permutation(k);
//		for (int i : kk) {
//			cout << i << " ";
//		}
//		cout << "\n";
//	}
//}

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