Submission #707544

#	Time	Username	Problem	Language	Result	Execution time	Memory
707544		600Mihnea	Permutation (APIO22_perm)	C++17	100 / 100	15 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 normalize({});
	}
	if (total == 2)
	{
		return normalize({ 0 });
	}
	if (total == 3)
	{
		return normalize({ 1, 0 });
	}
	assert(total / 4 >= 1);
	assert(total >= 4);
	vector<int> sol = construct_permutation(total / 4);
	const int INF = 10000;
	if (total % 4 == 0)
	{
		sol.push_back(INF);
		sol.push_back(INF + 1);
	}
	if (total % 4 == 1)
	{
		sol.push_back(INF);
		sol.push_back(INF + 1);
		sol.push_back(-1);
	}
	if (total % 4 == 2)
	{
		sol.push_back(INF);
		sol.push_back(-1);
		sol.push_back(INF + 1);
	}
	if (total % 4 == 3)
	{
		bool is1 = 0, is10 = 0;
		for (auto& x : sol)
		{
			is1 |= (x == 1);
			if (x == 0)
			{
				is10 |= is1;
			}
		}
		if (is10)
		{
			for (auto& x : sol) x *= 2;
			sol.push_back(INF);
			sol.push_back(INF + 1);
			sol.push_back(3);
		}
		else 
		{
			sol.push_back(INF);
			sol.push_back(-1);
			sol.push_back(INF + 1);
			sol.push_back(-2);
		}
	}
	return normalize(sol);
}

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