Submission #707536

#	Time	Username	Problem	Language	Result	Execution time	Memory
707536		600Mihnea	Permutation (APIO22_perm)	C++17	91.33 / 100	12 ms	344 KiB

perm

#include "perm.h"
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

typedef long long ll;

int get_nr_bits(ll x)
{
	if (x == 0)
	{
		return 0;
	}
	assert(x >= 1);
	return get_nr_bits(x / 2) + x % 2;
}

vector<int> normalize(vector<int> v)
{
	map<int, int> mp;
	for (auto& x : v)
	{
		mp[x] = 0;
	}
	int y = 0;
	for (auto& it : mp)
	{
		it.second = y++;
	}
	for (auto& x : v)
	{
		x = mp[x];
	}
	return v;
}

vector<int> construct_permutation(ll total)
{
	if (total == 1)
	{
		return {};
	}
	vector<int> perm;
	while (1)
	{
		int sz = (int)perm.size();
		int next_sz = 1 + sz;
		if ((1LL << next_sz) <= total)
		{
			perm.push_back(sz);
		}
		else
		{
			break;
		}
	}
	int curval = (int)1e9 + 7;
	ll cur = (1LL << (int)perm.size());
	while (cur < total)
	{
		for (int i = (int)perm.size() - 1; i >= -1; i--)
		{
			int small = 0;
			for (int j = 0; j <= i; j++)
			{
				small += (perm[j] <= 100);
			}
			if (small != i + 1)
			{
				continue;
			}
			if (cur + (1LL << small) <= total)
			{
				cur += (1LL << small);
				vector<int> nperm;
				for (int j = 0; j <= i; j++)
				{
					nperm.push_back(perm[j]);
				}
				nperm.push_back(curval++);
				for (int j = i + 1; j < (int)perm.size(); j++)
				{
					nperm.push_back(perm[j]);
				}
				perm = nperm;
				break;
			}
		}
	}
	assert(cur == total);
	perm = normalize(perm);
	return perm;
	for (auto& p : perm)
	{
		cout << p << " ";
	}
	exit(0);
	for (int k = 1; 1; k++)
	{
		ll rem = total + (k - 1);
		int nr_bits = get_nr_bits(rem);
		if (k < nr_bits)
		{
			continue;
		}
		if (rem & (1LL << 0))
		{
			continue;
		}
		// split rem into nr_bits bits
		assert(k >= nr_bits);
		vector<int> dims;
		for (int i = 1; (1LL << i) <= rem; i++)
		{
			if (rem & (1LL << i))
			{
				dims.push_back(i);
			}
		}
		int need_extra = k - nr_bits;
		for (int i = 0; i < (int)dims.size(); i++)
		{
			while (dims[i] >= 2 && need_extra > 0)
			{
				dims.push_back(dims[i] - 1);
				dims[i]--;
				need_extra--;
			}
		}
		assert(need_extra == 0);
		int sumtotal = 0;
		for (auto& d : dims)
		{
			sumtotal += d;
		}
		vector<int> sol;
		for (auto& x : dims)
		{
			sumtotal -= x;
			for (int i = 0; i < x; i++)
			{
				sol.push_back(sumtotal + i);
			}
		}
		//cout << " : ";
		//for (auto& x : sol)
		//{
		//	cout << x << " ";
		//}
		//cout << "\n";
		return sol;
	}
	return {};
}

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