Submission #742055

#	Time	Username	Problem	Language	Result	Execution time	Memory
742055		t6twotwo	Permutation (APIO22_perm)	C++17	98.33 / 100	88 ms	9312 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
map<ll, int> mp;
map<ll, int> q;
int solve(ll n) {
    if (n == 1) {
        return 0;
    }
	if (n == 2) {
		q[2] = 2;
		return 1;
	}
	if (n == 3) {
		q[3] = 3;
		return 2;
	}
    if (mp.count(n)) {
        return mp[n];
    }
	q[n] = 2;
    if (n % 2 == 0) {
        mp[n] = solve(n / 2) + 1;
	} else {
		mp[n] = solve(n / 2) + 2;
	}
	if (n % 4 == 1) {
		int x = solve(n / 4) + 3;
		if (x < mp[n]) {
			mp[n] = x;
			q[n] = 4;
		}
	} else if (n % 4 == 2) {
		int x = solve(n / 4) + 3;
		if (x < mp[n]) {
			mp[n] = x;
			q[n] = 4;
		}
	}
    if (n % 3 == 0) {
		int x = solve(n / 3) + 2;
		if (x < mp[n]) {
			mp[n] = x;
			q[n] = 3;
		}
    } else {
		int x = solve(n / 3) + 3;
		if (x < mp[n]) {
			mp[n] = x;
			q[n] = 3;
		}
    }
    return mp[n];
}
vector<int> construct_permutation(ll k) {
	solve(k);
	vector<int> t;
	while (k > 1) {
		if (q[k] == 2) {
			t.push_back(k % 2);
			k /= 2;
		} else if (q[k] == 3) {
			t.push_back(2 + k % 3);
			k /= 3;
		} else {
			t.push_back(5 + k % 4);
			k /= 4;
		}
	}
	vector<int> ans;
	int v = 0, u = -1;
	for (int i = t.size() - 1; i >= 0; i--) {
		if (t[i] == 0) {
			ans.push_back(v++);
		} else if (t[i] == 1) {
			ans.push_back(v++);
			ans.push_back(u--);
		} else if (t[i] == 2) {
			ans.push_back(v + 1);
			ans.push_back(v);
			v += 2;
		} else if (t[i] == 3) {
			ans.push_back(v + 1);
			ans.push_back(v);
			ans.push_back(u--);
			v += 2;
		} else if (t[i] == 4) {
			ans.push_back(v + 1);
			ans.push_back(u--);
			ans.push_back(v);
			v += 2;
		} else if (t[i] == 5) {
			ans.push_back(v++);
			ans.push_back(u--);
			ans.push_back(v++);
		} else{
			ans.push_back(v++);
			ans.push_back(v++);
			ans.push_back(u--);
		}
	}
	int add = -*min_element(ans.begin(), ans.end());
	for (int &x : ans) {
		x += add;
	}
	return ans;
}

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