oj.uz

Submission #576823

# Submission time Handle Problem Language Result Execution time Memory
576823 2022-06-13T15:24:49 Z dutinmeow Permutation (APIO22_perm) C++17
100 / 100
 2 ms 384 KB 
#include "perm.h"

#include <bits/stdc++.h>
using namespace std;

namespace permutation {
	vector<int> construct_permutation_slow(long long k) {
		vector<int> ret(k - 1);
		for (int i = 0; i < k - 1; i++)
			ret[i] = k - 2 - i;
		return ret;
	}
	
	const array<int, 5> primes = {2, 3, 5, 7, 11};

	vector<int> construct_permutation_dumb(long long k) {
		if (k <= 3)
			return construct_permutation_slow(k);
		for (int p : primes) {
			if (k % p != 0 || k == p)
				continue;
			auto ret = construct_permutation_dumb(k / p);
			auto tem = construct_permutation_dumb(p);
			int r = ret.size();
			for (int t : tem)
				ret.push_back(t + r);
			return ret;
		}
		auto ret = construct_permutation_dumb(k / 2);
		ret.push_back(ret.size());
		ret.insert(ret.begin(), ret.size());
		return ret;
	}
}

vector<int> construct_permutation(long long k) { 
	if (k <= 90)
		return permutation::construct_permutation_slow(k);
	else 
		return permutation::construct_permutation_dumb(k);
}

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 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 340 KB Output is correct