oj.uz

Submission #1035313

# Submission time Handle Problem Language Result Execution time Memory
1035313 2024-07-26T09:14:02 Z amine_aroua Permutation (APIO22_perm) C++17
66.1538 / 100
 11 ms 1820 KB 
#include "perm.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> bits;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myrand(ll l , ll r)
{
	return uniform_int_distribution<ll>(l , r)(rng);
}
void add(ll k)
{
	if(k == 0)
	{
		return;
	}
	ll last = 1;
	for(ll i = 59 ; i >= 1 ; i--)
	{
		if(k - ((1ll<<i) - 1) >= 0)
		{
			last = max(last , i);
		}
		if(k - ((1ll<<i) - 1) == 0)
		{
			bits.push_back(i);
			return;
		}
	}
	ll nb = myrand(max(1ll , last - 1) , last);
	k -= ((1ll<<nb) - 1);
	bits.push_back(nb);
	add(k);
}
std::vector<int> construct_permutation(long long k)
{
	k--;
	bits.clear();
	int n = 0;
	add(k);
	for(auto bit : bits)
		n+=bit;
	n--;
	vector<int> perm;
	for(auto i : bits)
	{
		for(int j = n - i + 1 ; j <= n ; j++)
		{
			perm.push_back(j);
		}
		n-=i;
	}
	return perm;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
56.153846151 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Partially correct 2 ms 344 KB Partially correct
4 Partially correct 1 ms 440 KB Partially correct
5 Partially correct 4 ms 860 KB Partially correct
6 Partially correct 4 ms 860 KB Partially correct
7 Partially correct 6 ms 1116 KB Partially correct
8 Partially correct 8 ms 1628 KB Partially correct
9 Partially correct 1 ms 348 KB Partially correct
10 Partially correct 9 ms 1820 KB Partially correct
11 Partially correct 8 ms 1372 KB Partially correct
12 Partially correct 7 ms 1372 KB Partially correct
13 Partially correct 11 ms 1312 KB Partially correct