oj.uz

Submission #596663

# Submission time Handle Problem Language Result Execution time Memory
596663 2022-07-15T00:23:53 Z slime Permutation (APIO22_perm) C++17
89.6154 / 100
 3 ms 340 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
79.615384614 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Partially correct 2 ms 340 KB Partially correct
6 Correct 2 ms 300 KB Output is correct
7 Partially correct 3 ms 340 KB Partially correct
8 Partially correct 2 ms 340 KB Partially correct
9 Partially correct 3 ms 340 KB Partially correct
10 Partially correct 3 ms 340 KB Partially correct
11 Partially correct 3 ms 340 KB Partially correct
12 Partially correct 2 ms 340 KB Partially correct
13 Partially correct 3 ms 340 KB Partially correct