Submission #1226842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226842		vyaduct	Permutation (APIO22_perm)	C++20	71.22 / 100	7 ms	1348 KiB

perm

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

#define vt vector
#define all(c) (c).begin(), (c).end()
#define pb push_back
const int MAXD = 60;

// finds (x) such that 2^x1-1 + 2^x2-1 + ... + 2^xn-1 = k
vector<int> build(ll k) {
  vector<int> res;
  while (k > 0) {
    int t = 63 - __builtin_clzll(k + 1);  
    res.push_back(t);
    k -= ( (1LL << t) - 1 );
  }
  return res;
}

vt<int> correctify(vt<int> b){
  int c=0;
  vt<int> res;
  for (auto x: b){
    for (int i=x-1;i>=0;i--) res.pb(i+c);
    c += x;
  }
  reverse(all(res));
  return res;
}

vt<int> construct_permutation(ll k) {
  k--;
  vt<int> ans;

  vt<int> b = build(k);
  sort(all(b));
  vt<int> c = correctify(b);

	return c;
}

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