Submission #718368

#	Time	Username	Problem	Language	Result	Execution time	Memory
718368		lam	Permutation (APIO22_perm)	C++17	10 / 100	1 ms	340 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;

long long count_inc(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],(ll)1e18+1);
  	}
  }
  long long result = 0;
  for (int i = 0; i <= (int)v.size(); i++){
  	result += dp[i];
  	result = min(result,(ll)1e18+1);
  }
  return result;
}
vector<int> construct_permutation(long long k)
{
    ll kk = k;
    vector <int> res;
    ll len = log2(k);
    vector <int> a;
    for (int i=1; i<=len; i++) a.push_back(i-1);
    k-=(1LL<<len);
    while (k>0)
    {
        ll it = 0;
        while ((1LL<<(it+1))<= k)
        {
            it++;
        }
        k-= (1LL<<it);
        a.push_back(it);
    }
    int n=a.size();
    vector <int> d(n+1,0);
    for (int i=0; i<n; i++) d[a[i]] ++;
    for (int i=1; i<=n; i++) d[i]+=d[i-1];
    res.resize(n);
    for (int i=0; i<n; i++) res[i] = --d[a[i]];
//    for (int i:a) cerr<<i<<' '; cerr<<endl;
//    for (int i:res) cerr<<i<<' '; cerr<<endl;
    vector <int> v=res;
    sort(v.begin(),v.end());
    for (int i=0; i<n; i++) assert(v[i]==i);
    ll ttemp = count_inc(res);
    assert(ttemp==kk);
    return res;
}

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