Submission #833505

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
833505	2023-08-22 06:18:44	makanhulia	Permutation (APIO22_perm)	C++17	71.22 / 100	10 ms	1364 KiB

perm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include "perm.h"
#include<bits/stdc++.h>
using namespace std;
long long binpow(long long base, int exp) {
  long long ret=1;
  while(exp) {
    if(exp&1) ret*=base;
    base*=base;
    exp>>=1;
  }
  return ret;
}
vector<int> construct_permutation(long long k) {
  vector<int> ans; k--;
  int mx=0;
  while(k) {
    int l=0, r=59, len=0;
    while(l<=r) {
      int mid=l+r>>1;
      if(binpow(2, mid)-1<=k) len=mid, l=mid+1;
      else r=mid-1;
    }
    mx-=len;
    for(int i=mx+1; i<=mx+len; i++) ans.push_back(i);
    k-=binpow(2, len)-1;
  }
  for(int &p : ans) p-=mx+1;
  return ans;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:19:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |       int mid=l+r>>1;
      |               ~^~

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