oj.uz

Submission #957687

# Submission time Handle Problem Language Result Execution time Memory
957687 2024-04-04T08:00:13 Z pragmatist Permutation (APIO22_perm) C++17
71.2154 / 100
 17 ms 1584 KB 
#include "perm.h"
#include<bits/stdc++.h>

using namespace std;

mt19937 rng(time(NULL));

std::vector<int> construct_permutation(long long k)
{
	vector<int> ans;
	k--;
	int n = 0;
	vector<pair<int, int> > v;
	while(k>0) {
		long long mx = 0;
		int x = -1, y = -1;
		for(int i = 1; i <= 60; ++i) {
			long long cur = (1ll<<i)-1;
			if(cur <= k) {
				if(cur>mx) {
					mx = cur;
					x = i;
					y = -1;
				}
			}
			for(int j = 1; j <= 60; ++j) {
				long long ruc = cur+(1ll<<j)-1;
				if(ruc<=k) {
					if(ruc>mx) {
						mx = ruc;
						x = i;
						y = j;
					}
				}
			}
		}
		if(y == -1) {
			long long cur = (1ll<<x)-1;
			k -= cur;
			n += x;
			v.push_back({n-x, n-1});
			continue;
		}
		long long c1 = (1ll<<x)-1;
		long long c2 = (1ll<<y)-1;
		k -= c1;
		k -= c2;
		n += x;
		v.push_back({n-x, n-1});
		n += y;
		v.push_back({n-y, n-1});
	}
	reverse(v.begin(), v.end());
	for(auto e : v) {
		int l = e.first;
		int r = e.second;
		for(int i = l; i <= r; ++i) {
			ans.push_back(i);
		}
	}
	return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
61.215384618 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Partially correct 2 ms 344 KB Partially correct
4 Partially correct 2 ms 348 KB Partially correct
5 Partially correct 7 ms 660 KB Partially correct
6 Partially correct 7 ms 564 KB Partially correct
7 Partially correct 11 ms 996 KB Partially correct
8 Partially correct 15 ms 1116 KB Partially correct
9 Correct 2 ms 348 KB Output is correct
10 Partially correct 17 ms 1584 KB Partially correct
11 Partially correct 13 ms 1116 KB Partially correct
12 Partially correct 12 ms 860 KB Partially correct
13 Partially correct 13 ms 1380 KB Partially correct