Submission #584529

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

perm

#include "perm.h"

using namespace std;

typedef vector<int> vi;

vi construct_permutation(long long k) {
	vi pp;
	if (k == 2)
		pp.push_back(0);
	else {
		int l = 0;
		while (1LL << l + 1 <= k)
			l++;
		if ((k & 1LL << l - 1) != 0)
			pp.push_back(1), pp.push_back(0), l -= 2;
		else if ((k & 1LL << l - 2) == 0)
			pp.push_back(2), pp.push_back(1), pp.push_back(0), l -= 3;
		else
			pp.push_back(3), pp.push_back(2), pp.push_back(1), pp.push_back(0), l -= 3;
		int n = pp.size();
		while (l > 0) {
			int b = k >> l - 1 & 3;
			if (b == 0)
				pp.push_back(n++), pp.push_back(n++);
			else if (b == 1) {
				pp.push_back(n++), pp.push_back(n++);
				for (int i = 0; i < n; i++)
					pp[i]++;
				pp.push_back(0), n++;
			} else if (b == 2) {
				pp.push_back(n++);
				for (int i = 0; i < n; i++)
					pp[i]++;
				pp.push_back(0), n++;
				pp.push_back(n++);
			} else {
				pp.push_back(n++), pp.push_back(n++);
				for (int i = 0; i < n; i++)
					if (pp[i] >= 2)
						pp[i]++;
				pp.push_back(2), n++;
			}
			l -= 2;
		}
		if (l == 0) {
			pp.push_back(n++);
			if ((k & 1) == 1) {
				for (int i = 0; i < n; i++)
					pp[i]++;
				pp.push_back(0);
			}
		}
	}
	return pp;
}

Compilation message (stderr)

perm.cpp: In function 'vi construct_permutation(long long int)':
perm.cpp:13:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   13 |   while (1LL << l + 1 <= k)
      |                 ~~^~~
perm.cpp:15:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   15 |   if ((k & 1LL << l - 1) != 0)
      |                   ~~^~~
perm.cpp:17:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   17 |   else if ((k & 1LL << l - 2) == 0)
      |                        ~~^~~
perm.cpp:23:19: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   23 |    int b = k >> l - 1 & 3;
      |                 ~~^~~

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