Submission #881682

#	Time	Username	Problem	Language	Result	Execution time	Memory
881682		tsumondai	Permutation (APIO22_perm)	C++17	0 / 100	122 ms	262144 KiB

perm

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

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e6 + 5;

const int oo = 1e9, mod = 1e9 + 7;

int n, m, k;
string s;
vector<int> arr;

void apply_gadget(vector<int>& v, const vector<int>& gadget) {
	vector<int> gadget_items;
	for (int x : gadget) if (x > 0) gadget_items.push_back(x);
	sort(gadget_items.begin(), gadget_items.end());

	for (int x : gadget_items)
		for (int& y : v)
			if (y >= x) y++;

	int n_size = v.size() + gadget.size();
	for (int x : gadget) {
		if (x <= 0) v.push_back(n_size + x);
		else v.push_back(x);
	}
}

vector<int> dec2bin(int x) {
	vector<int> result;
	while (x > 0) result.push_back(x % 2); x /= 2;
	reverse(result.begin(), result.end());
	return result;
}

vector<int> permutation(int k) {
	if (k == 1) return vector<int>();
	if (k == 2) return vector<int>({1});
	if (k == 3) return vector<int>({2, 1});

	vector<int> bin_k = dec2bin(k);
	vector<int> result;
	int p = 1;
	if (bin_k[p] == 0) {
		if (bin_k[p + 1] == 0) result = vector<int>({3, 2, 1});
		if (bin_k[p + 1] == 1) result = vector<int>({2, 3, 1});
		p += 2;
	}
	else { result = vector<int>({2, 1}); p++; }

	while (p + 1 < (int)bin_k.size()) {
		if (bin_k[p] == 0) {
			apply_gadget(result, vector<int>({0}));
			p++;
		}
		else {
			if (bin_k[p + 1] == 0)
				apply_gadget(result, vector<int>({ -1, 1, 0}));
			else
				apply_gadget(result, vector<int>({ -1, 0, 3}));
			p += 2;
		}
	}
	if (p < (int)bin_k.size()) {
		if (bin_k[p] == 0)
			apply_gadget(result, vector<int>({0}));
		if (bin_k[p] == 1)
			apply_gadget(result, vector<int>({0, 1}));
		p++;
	}
	return result;
}

vector<int> construct_permutation(long long k) {
	vector<int> result = permutation(k);
	for (int i = 0; i < result.size(); i++)
		result[i]--;
	return result;
}

/*signed main() {
    cin.tie(0)->sync_with_stdio(false);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    //process();
    cerr << "Time elapsed: " << __TIME << " s.\n";
    return 0;
}*/

/*
Xét các trường hợp đặc biệt
Kiểm tra lại input/output
Cố gắng trâu
Lật ngược bài toán
Keep calm and get VOI
Flow:

*/

Compilation message (stderr)

perm.cpp: In function 'std::vector<long long int> dec2bin(long long int)':
perm.cpp:44:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   44 |  while (x > 0) result.push_back(x % 2); x /= 2;
      |  ^~~~~
perm.cpp:44:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   44 |  while (x > 0) result.push_back(x % 2); x /= 2;
      |                                         ^
perm.cpp: In function 'std::vector<long long int> construct_permutation(long long int)':
perm.cpp:89:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for (int i = 0; i < result.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~

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