Submission #881692

#	Time	Username	Problem	Language	Result	Execution time	Memory
881692		tsumondai	Permutation (APIO22_perm)	C++17	100 / 100	2 ms	604 KiB

perm

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

#pragma comment(linker, "/stack:336777216")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#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;
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(long long 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(long long 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:5: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    5 | #pragma comment(linker, "/stack:336777216")
      | 
perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for (int i = 0; i < result.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~

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