oj.uz

Submission #789672

# Submission time Handle Problem Language Result Execution time Memory
789672 2023-07-21T17:16:36 Z GusterGoose27 Permutation (APIO22_perm) C++17
100 / 100
 51 ms 340 KB 
#include "perm.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int test = 9;
const int max_use = 100;

vector<int> table[(1 << test)+1];
bool made = 0;

void construct(ll k, int s, deque<int> &ans) {
	if (k == 1) return;
	for (int i = 2; i <= max_use; i++) {
		if (table[i].empty() || !(k%i == 0)) continue;
		construct(k/i, s+table[i].size(), ans);
		for (int j = table[i].size()-1; j >= 0; j--) ans.push_front(s+table[i][j]);
		return;
	}
	construct(k-1, s+1, ans);
	ans.push_back(s);
}

bool vis[test];
int bit[test+1];

void upd(int p, int v, int n) {
	for (; p <= n; p |= (p+1)) bit[p] += v;
}

int sum(int p) {
	int s = 0;
	for (p++; p > 0; p &= (p-1)) s += bit[p-1];
	return s;
}

int get_sub(vector<int> &v) {
	int n = v.size();
	fill(bit, bit+n+1, 0);
	upd(0, 1, n);
	for (int i = 0; i < n; i++) {
		upd(v[i]+1, sum(v[i]+1), n);
	}
	return sum(n);
}

void make_perm(int n, vector<int> &v) {
	if (v.size() == n) {
		int inc = get_sub(v);
		if (table[inc].size() == 0 || v.size() < table[inc].size()) table[inc] = v;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
		vis[i] = 1;
		v.push_back(i);
		make_perm(n, v);
		v.pop_back();
		vis[i] = 0;
	}
}

void make_basic() {
	for (int i = 1; i <= test; i++) {
		vector<int> v;
		make_perm(i, v);
	}
}

void print(vector<int> &v) {
	for (int p: v) cout << ' ' << p;
	cout << '\n';
}

vector<int> construct_permutation(ll k) {
	if (!made) {
		make_basic();
		made = 1;
	}
	// for (int i = 2; i < 10; i++) {
	// 	cout << i << ":"; print(table[i]);
	// }
	deque<int> ans;
	construct(k, 0, ans);
	vector<int> v;
	for (int p: ans) v.push_back(p);
	return v;
}

Compilation message

perm.cpp: In function 'void make_perm(int, std::vector<int>&)':
perm.cpp:51:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |  if (v.size() == n) {
      |      ~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 320 KB Output is correct
2 Correct 49 ms 320 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 320 KB Output is correct
2 Correct 49 ms 320 KB Output is correct
3 Correct 50 ms 340 KB Output is correct
4 Correct 49 ms 320 KB Output is correct
5 Correct 49 ms 320 KB Output is correct
6 Correct 50 ms 332 KB Output is correct
7 Correct 50 ms 316 KB Output is correct
8 Correct 51 ms 336 KB Output is correct
9 Correct 50 ms 304 KB Output is correct
10 Correct 50 ms 316 KB Output is correct
11 Correct 51 ms 316 KB Output is correct
12 Correct 50 ms 316 KB Output is correct
13 Correct 50 ms 316 KB Output is correct