oj.uz

Submission #584529

# Submission time Handle Problem Language Result Execution time Memory
584529 2022-06-27T14:05:23 Z rainboy Permutation (APIO22_perm) C++17
100 / 100
 2 ms 340 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct