| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 738735 | shantol | Permutation (APIO22_perm) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "perm.h"
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef array<int,3> triple;
#define log(x) 32 - __builtin_clz(x) - 1
#define ff first
#define sc second
#define pb push_back
#define gcd(x,y) __gcd(x,y)
#define lcm(x,y) x*(y/gcd(x,y))
#define mx(m) *max_element(m.begin(),m.end())
#define mn(m) *min_element(m.begin(),m.end())
#define fr(i,n) for(ll i=0;i<n;i++)
#define rfr(i,n) for(ll i=n-1;i>=0;i--)
#define cmp compare
#define elif else if
#define minv(x,y) (x<y? x:y)
#define vctr vector<ll>
#define pii vector<pair<int,int>>
#define srt(a) sort(a.begin(),a.end())
#define rsrt(a) sort(a.rbegin(),a.rend())
#define sum(a) accumulate(a.begin(),a.end(),0)
#define chk(a,x) find(a.begin(),a.end(),x)!=a.end()
#define inf LLONG_MAX
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl '\n'
#define inv(x,mod) powermod(x,mod-2,mod)
#define sz size()
#define pi M_PI
ll pw(ll n,ll p){return (p>=n?p:pw(n,p<<1));}
//fill(&a[0][0],&a[0][0]+100000*512,100000) a[100000][512]
//const ll N=500*10000+13;
//ll p[N];
const ll mod=1e9+7;
ll powermod(ll x,ll y,ll mod)
{
ll res=1;
while(y>0)
{
if(y&1)
{
if(mod)
{
res=(res*x)%mod;
}
else
{
res*=x;
}
}
y>>=1;
if(mod)
{
x=(x*x)%mod;
}
else
{
x*=x;
}
}
return res;
}
/*vector<int> tr;
vector<int> b;
void build(int low,int high,int pos)
{
if(low==high)
{
tr[pos]=b[low];
}
else
{
int mid=(low+high)/2;
build(low,mid,pos*2+1);
build(mid+1,high,pos*2+2);
tr[pos]=max(tr[pos*2+1],tr[pos*2+2]);
}
}
int query(int low,int high,int st,int en,int pos)
{
if(low>en || high<st)return 0;
if(low>=st && high<=en)
{
return tr[pos];
}
int mid=(low+high)/2;
return max(query(low,mid,st,en,pos*2+1),query(mid+1,high,st,en,pos*2+2));
}
void update(int low,int high,int ind,int val,int pos)
{
if(low>ind || high<ind)return;
if(low==high)tr[pos]+=val;
else
{
int mid=(low+high)/2;
update(low,mid,ind,val,pos*2+1);
update(mid+1,high,ind,val,pos*2+2);
tr[pos]=tr[pos*2+1]+tr[pos*2+2];
}
}*/
/*void solve()
{
}*/
int* construct_permutation(ll k){
vector<int> ans;
k--;
for(ll p=1, i=0;p<=k;i++,p=(p<<1)|1){
ans.pb(i);
}
ll p=ans.sz;
vector<vector<int>> v(p+1);
k=k-(1<<p)+1;
for(int i=ans.sz-1;i>=0;i--){
while(k>=(1<<i)){
v[i].pb(p++);
k-=(1<<i);
}
}
vector<int> val;
for(int i=0;i<ans.sz;i++){
for(int j:v[i])val.pb(j);
val.pb(ans[i]);
}
int* a=new int[val.sz];
for(int i=0;i<val.sz;i++)a[i]=val[i];
return a;
}
/*int main()
{
fast;
/*int *ptr=construct_permutation(12);
for(int i=0;i<val.sz;i++)cout<<ptr[i]<<' ';
int t=1;
cin>>t;
while(t--)solve();
}*/