Submission #789672

#	Time	Username	Problem	Language	Result	Execution time	Memory
789672		GusterGoose27	Permutation (APIO22_perm)	C++17	100 / 100	51 ms	340 KiB

perm

#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 (stderr)

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 / 10
• Subtask 2: 90 / 90