Submission #1103778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103778		epicci23	Permutation (APIO22_perm)	C++17	100 / 100	277 ms	64328 KiB

perm

#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
#include "perm.h"

map<long long,vector<int>> cache;

vector<int> f(long long x){
  if(x==1) return {};
  if(cache.count(x)) return cache[x];

  if(x%2==0){
    vector<int> u = f(x/2);
    u.push_back(sz(u));
    return cache[x]=u;
  }

  vector<int> res = f(x/2);
  for(int i=0;i<sz(res);i++) res[i]++;
  res.push_back(sz(res)+1);
  res.push_back(0);

  for(int val : {3,5,7}){
    if(x%val) continue;
    vector<int> cur = f(x/val);
    if(sz(cur)+val-1<sz(res)){
      res=cur;
      cur.clear();
      int p=sz(res)+val-2;
      for(int j=1;j<val;j++) res.push_back(p--);
    }
  }

  return cache[x]=res;
}

vector<int> construct_permutation(long long k){
  return f(k);
}



/*void _(){
  int k;
  cin >> k;
  
  vector<int> ans = f(k);
  cout << sz(ans) << '\n';
  for(int x:ans) cout << x << ' ';
  cout << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

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