oj.uz

Submission #1035268

# Submission time Handle Problem Language Result Execution time Memory
1035268 2024-07-26T08:17:49 Z amine_aroua Permutation (APIO22_perm) C++17
71.2154 / 100
 161 ms 1108 KB 
#include "perm.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
std::vector<int> construct_permutation(long long k)
{
	int sz = 10000;
	vector<int> best;
	for(ll l = 1 ;l < 100 ;l++)
	{
		ll x = k + l - 1;
		if(__builtin_popcountll(x) <= l)
		{
			int n = 0;
			multiset<int> bits;
			for(ll i = 0 ; i < 61 ; i++)
			{
				if((1ll<<i) & x)
				{
					bits.insert(i);
				}
			}
			bool ok = 1;
			while ((int)bits.size() < l)
			{
				auto it = upper_bound(bits.begin() , bits.end() ,0);
				if(it == bits.end())
				{
					ok = 0;
					break;
				}
				int val = *it;
				bits.erase(it);
				bits.insert(val - 1);
				bits.insert(val - 1);
			}
			if(!ok)
				continue;
			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;
			}
			if((int)perm.size() < sz)
			{
				sz = (int)perm.size();
				best = perm;
			}
		}
	}
	return best;
}
/*
int main()
{
	for(int k = 7 ; k <= 7 ; k++)
	{
		vector<int> v =construct_permutation(k);
		if(v != vector<int>({-1}))
			cout<<"OK "<<k<<'\n';
		else
			cout<<"WA "<<k<<'\n';
	}
}
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
61.215384618 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 132 ms 428 KB Output is correct
3 Partially correct 161 ms 424 KB Partially correct
4 Partially correct 158 ms 344 KB Partially correct
5 Partially correct 149 ms 692 KB Partially correct
6 Partially correct 153 ms 716 KB Partially correct
7 Partially correct 147 ms 796 KB Partially correct
8 Partially correct 133 ms 884 KB Partially correct
9 Correct 152 ms 344 KB Output is correct
10 Partially correct 135 ms 1108 KB Partially correct
11 Partially correct 152 ms 972 KB Partially correct
12 Partially correct 150 ms 852 KB Partially correct
13 Partially correct 155 ms 852 KB Partially correct