oj.uz

Submission #596676

# Submission time Handle Problem Language Result Execution time Memory
596676 2022-07-15T00:47:21 Z slime Permutation (APIO22_perm) C++17
91.3333 / 100
 169 ms 460 KB 
#include "perm.h"
#include "bits/stdc++.h"
using namespace std;
static long long MX=1e18;

long long count_increasing(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],MX+1);
  	}
  }
  long long result = 0;
  for (int i = 0; i <= (int)v.size(); i++){
  	result += dp[i];
  	result = min(result,MX+1);
  }
  return result;
}

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

std::vector<int> construct_permutation(long long k)
{
  vector<int> cur = {};
  
  cur.push_back(0); 
  for(int i = 1; ; i++) {
    int lb = 0, rb = cur.size();
    if(count_increasing(cur) == k) {
      return cur;
    }
    while(lb < rb) {
      int mid = (lb + rb + 1) >> 1;
      vector<int> now;
      for(int j=0; j<mid; j++) now.push_back(cur[j]);
      now.push_back(i);
      for(int j=mid; j<cur.size(); j++) now.push_back(cur[j]);
      if(count_increasing(now) <= k) lb = mid;
      else rb = mid - 1;
    }
    vector<int> now;
    for(int j=0; j<lb; j++) now.push_back(cur[j]);
    now.push_back(i);
    for(int j=lb; j<cur.size(); j++) now.push_back(cur[j]);
    cur = now;
  }
  return cur;
 
}
// 576460752303423487

Compilation message

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |       for(int j=mid; j<cur.size(); j++) now.push_back(cur[j]);
      |                      ~^~~~~~~~~~~
perm.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int j=lb; j<cur.size(); j++) now.push_back(cur[j]);
      |                   ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
81.333333333 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 4 ms 300 KB Output is correct
4 Correct 11 ms 316 KB Output is correct
5 Partially correct 72 ms 328 KB Partially correct
6 Correct 37 ms 320 KB Output is correct
7 Correct 73 ms 324 KB Output is correct
8 Partially correct 130 ms 460 KB Partially correct
9 Correct 50 ms 316 KB Output is correct
10 Partially correct 169 ms 320 KB Partially correct
11 Partially correct 122 ms 332 KB Partially correct
12 Partially correct 102 ms 328 KB Partially correct
13 Partially correct 145 ms 340 KB Partially correct