Submission #576566

#	Time	Username	Problem	Language	Result	Execution time	Memory
576566		8e7	Permutation (APIO22_perm)	C++17	100 / 100	2 ms	340 KiB

perm

//Challenge: Accepted
//#define _GLIBCXX_DEBUG 1
#include "perm.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 128
#define mod 998244353
#define pii pair<int, int>
#define ff first
#define ss second
const int inf = 1e9;
std::vector<int> construct_permutation(long long k) {
	vector<int> bits, arr, res;
	while (k) {
		bits.push_back(k & 1);
		k >>= 1;
	}
	reverse(bits.begin(), bits.end());
	int type = 0;
	for (int i = 1;i < bits.size();i += 2) {
		if (i + 1 >= bits.size()) {
			type = bits[i] + 1;	
		} else {
			arr.push_back(bits[i] * 2 + bits[i+1]);
		}
	}
	for (int i:arr) {
		int n = res.size();
		if (i == 0) {
			res.push_back(n);
			res.push_back(n+1);
		} else if (i == 1) {
			res.push_back(n);
			res.push_back(n+1);
			for (int &j:res) j++;
			res.push_back(0);
		} else if (i == 2) {
			res.push_back(n);
			for (int &j:res) j++;
			res.push_back(0);
			res.push_back(n+2);
		} else {
			int p0 = 0, p1 = 0;
			for (int j = 0;j < n;j++) {
				if (res[j] == 0) p0 = j; 
				if (res[j] == 1) p1 = j;
			}
			if (p1 < p0) {
				res.push_back(n);
				res.push_back(n+1);
				for (int &j:res) {
					if (j > 1) j++;
				}
				res.push_back(2);
			} else {
				res.push_back(n);
				for (int &j:res) j++;
				res.push_back(0);
				res.push_back(n+2);
				for (int &j:res) j++;
				res.push_back(0);
			}
		}
	}
	if (type == 1) res.push_back(res.size());
	else if (type == 2) {
		res.push_back(res.size());
		for (int &j:res) j++;
		res.push_back(0);
	}
	pary(res.begin(), res.end());
	return res;
}

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (int i = 1;i < bits.size();i += 2) {
      |                 ~~^~~~~~~~~~~~~
perm.cpp:34:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   if (i + 1 >= bits.size()) {
      |       ~~~~~~^~~~~~~~~~~~~~
perm.cpp:16:19: warning: statement has no effect [-Wunused-value]
   16 | #define pary(...) 0
      |                   ^
perm.cpp:84:2: note: in expansion of macro 'pary'
   84 |  pary(res.begin(), res.end());
      |  ^~~~

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