#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define ull unsigned ll
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> distr;
ll rnd(ll a, ll b){return distr(rng)%(b-a+1)+a;}
#include "perm.h"
std::vector<int> construct_permutation(long long k){
vector<int>ans;
vector<int>vale;
ll e = 0;
while(k != 1){
if((k % 3) == 0){
k /= 3;
vale.pb(1);
e++;
}
else if((k % 2) == 0){
k /= 2;
vale.pb(2);
}
else if((k % 5) == 0){
k /= 5;
vale.pb(3);
e += 2;
}
else if((k % 7) == 0){
k /= 7;
vale.pb(4);
e += 3;
}
else{
vale.pb(0);
k--;
}
}
ll n = vale.size() + e;
ll l = 0,r = n-1;
for(auto x:vale){
if(x == 0){
ans.pb(l);
l++;
}
else if(x == 2){
ans.pb(r);
r--;
}
else if(x == 1){
ans.pb(r - 1);
ans.pb(r);
r -= 2;
}
else if(x == 3){
ans.pb(r - 1);
ans.pb(r - 2);
ans.pb(r);
r -= 3;
}
else if(x == 4){
ans.pb(r - 3);
ans.pb(r - 1);
ans.pb(r);
ans.pb(r - 2);
r -= 4;
}
}
reverse(all(ans));
return ans;
}
/*
static long long MX=1e18;
static bool check_permutation(vector<int> v)
{
sort(v.begin(),v.end());
for(int i=0;i<v.size();i++)
if(v[i]!=i) return 0;
return 1;
}
long long count_increasing(const vector<int>& v) {
vector<long long> dp(v.size() + 1, 0);
dp[0] = 1;
for (int x : v)
{
for (int i = 0; i <= x; i++)
{
dp[x+1] += dp[i];
dp[x+1] = min(dp[x+1],MX+1);
}
}
long long result = 0;
for (int i = 0; i <= (int)v.size(); i++){
result += dp[i];
result = min(result,MX+1);
}
return result;
}
int main() {
int t;
while(1)
{
long long k;
k = rnd(2,MX);
vector<int> ret=construct_permutation(k);
if(!check_permutation(ret))
{
printf("WA: Returned array is not a permutation\n");
exit(0);
}
long long inc=count_increasing(ret);
if(inc!=k)
{
if(inc==MX+1)
printf("WA: Expected %lld increasing subsequences, found more than %lld\n",k, MX);
else
printf("WA: Expected %lld increasing subsequences, found %lld\n",k,inc);
exit(0);
}
if((int)ret.size() > 97){
cout<<ret.size()<<" "<<k<<endl;
return 0;
}
}
return 0;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
2 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
2 ms |
340 KB |
Output is correct |
