Submission #740873

#	Time	Username	Problem	Language	Result	Execution time	Memory
740873		LittleCube	Permutation (APIO22_perm)	C++17	100 / 100	2 ms	344 KiB

perm

#include "perm.h"
#ifndef EVAL
#include "perm_grader.cpp"
#endif
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;

vector<int> construct_permutation(long long k)
{
	vector<int> f, s, dp;
	int n = 0;
	ll ans = 0;
	while (k > 1)
	{
		if (k % 3 == 0)
		{
			f.emplace_back(n + 1);
			f.emplace_back(n);
			n += 2;
			k /= 3;
		}
		// else if(k % 3 == 0)
		// {
		// 	f.emplace_back(n);
		// 	f.emplace_back(n + 1);
		// 	n++;
		// }
		else if (k % 2 == 0)
		{
			f.emplace_back(n);
			n++;
			k /= 2;
		}
		else if (k % 5 == 0)
		{
			f.emplace_back(n + 1);
			f.emplace_back(n + 2);
			f.emplace_back(n);
			n += 3;
			k /= 5;
		}
		else if (k % 7 == 0)
		{
			f.emplace_back(n + 2);
			f.emplace_back(n + 3);
			f.emplace_back(n);
			f.emplace_back(n + 1);
			n += 4;
			k /= 7;
		}
		else
		{
			s.emplace_back(n);
			n++;
			k--;
		}
	}

	while (!s.empty())
	{
		f.emplace_back(s.back());
		s.pop_back();
	}

	dp.resize(f.size());
	for (int i = 0; i < f.size(); i++)
	{
		dp[i] = 1;
		for (int j = 0; j < i; j++)
			if (f[j] < f[i])
				dp[i] += dp[j];
		ans += dp[i];
	}
	cerr << ans << '\n';
	return f;
}

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for (int i = 0; i < f.size(); i++)
      |                  ~~^~~~~~~~~~

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