Submission #596663

#	Time	Username	Problem	Language	Result	Execution time	Memory
596663		slime	Permutation (APIO22_perm)	C++17	89.62 / 100	3 ms	340 KiB

perm

#include "perm.h"
#include "bits/stdc++.h"
using namespace std;

int fastlog(long long x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}

std::vector<int> construct_permutation(long long k)
{
  // x3: 2 0 1 "4 3"
  // x6: 2 0 1 "4 3 5"
  // +1: "3" 2 0 1
  // +2: "4 3" 2 0 1
  vector<int> cur = {};
  vector<int> bit;
  bool begin = 0;
  long long pow3[38];
  pow3[0] = 1;
  for(int i=1; i<38; i++) pow3[i] = pow3[i-1] * 3;
  long long kpr = k;
  for(int i = 37; i >= 0; i--) {
    if(kpr >= pow3[i]) {
      bit.push_back(kpr / pow3[i]);

      begin = 1;
      kpr %= pow3[i];
    }
    else if(begin) bit.push_back(0);
  }
  if(bit[0] == 2) {
    cur.push_back(0);
  }
  for(int i = 1; i < bit.size(); i++) {
    int n = cur.size();

    cur.push_back(n + 1);
    cur.push_back(n);

    for(int j = 0; j < bit[i]; j++) {
      int n = cur.size();
      vector<int> nw;
      nw.push_back(n);
      for(int x: cur) nw.push_back(x);
      cur = nw;
    }
    
  }

  return cur;
 
}

Compilation message (stderr)

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

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