Submission #742045

#	Time	Username	Problem	Language	Result	Execution time	Memory
742045		t6twotwo	Permutation (APIO22_perm)	C++17	98.33 / 100	32 ms	4356 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 (mp.count(n)) {
        return mp[n];
    }
    if (n % 2 == 0) {
        return mp[n] = solve(n / 2) + 1;
    }
    mp[n] = solve(n / 2) + 2;
    if (n % 3 == 0) {
		int x = solve(n / 3) + 2;
		if (x < mp[n]) {
			mp[n] = x;
			q[n] = 1;
		}
    } else {
		int x = solve(n / 3) + 3;
		if (x < mp[n]) {
			mp[n] = x;
			q[n] = 1;
		}
    }
    return mp[n];
}
vector<int> construct_permutation(ll k) {
	solve(k);
	vector<int> t;
	while (k > 1) {
		if (!q[k]) {
			t.push_back(-2 + k % 2);
			k /= 2;
		} else {
			t.push_back(k % 3);
			k /= 3;
		}
	}
	vector<int> ans;
	int v = 0, u = -1;
	for (int i = t.size() - 1; i >= 0; i--) {
		if (t[i] == -2) {
			ans.push_back(v++);
		} else if (t[i] == -1) {
			ans.push_back(v++);
			ans.push_back(u--);
		} else if (t[i] == 0) {
			ans.push_back(v + 1);
			ans.push_back(v);
			v += 2;
		} else if (t[i] == 1) {
			ans.push_back(v + 1);
			ans.push_back(v);
			ans.push_back(u--);
			v += 2;
		} else {
			ans.push_back(v + 1);
			ans.push_back(u--);
			ans.push_back(v);
			v += 2;
		}
	}
	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