oj.uz

답안 #596708

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
596708 2022-07-15T01:42:07 Z slime 순열 (APIO22_perm) C++17
100 / 100
 5 ms 352 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);
}

mt19937_64 rng((long long)std::chrono::steady_clock::now().time_since_epoch().count());
long long rnd(long long x, long long y) {
  long long u = uniform_int_distribution<long long>(x, y)(rng); return u;
}

std::vector<int> construct_permutation(long long k)
{
  
  if(k == 1) return {};
  if(k == 2) return {0};
  if(k == 3) return {1, 0};
  if(k == 4) return {0, 1};

  //cout << "Solve(" << k <<")\n";
  long long x, c, rem = 1e9;
  for(long long i = 2; i < min(20ll, k); i++) {
    if(k % i < rem) {
      rem = k % i;
      x = i;
      c = k / i;
    }
  }
  //cout << x << " " << c << " " << rem << "\n";
  vector<int> cur = {};
  
  vector<int> l = construct_permutation(c);
  vector<int> r = construct_permutation(x);
  for(int q: l) cur.push_back(q);
  for(int q: r) cur.push_back(q + (int) l.size());
  int n = cur.size();
  vector<int> now;
  for(int i=rem-1; i>=0; i--) now.push_back(i + n);
  for(int q: cur) now.push_back(q);
  cur = now;
  return cur;


  
 
}

Compilation message

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:54:42: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |   vector<int> l = construct_permutation(c);
      |                                          ^
perm.cpp:55:42: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |   vector<int> r = construct_permutation(x);
      |                                          ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
90.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 236 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 4 ms 352 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 4 ms 340 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Correct 4 ms 340 KB Output is correct