#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
const int MOD=1e9+7;
int n;
long long num[63];
long long ft[201];
void upd(int x,long long v){
while (x<=n){
ft[x]+=v;
if (ft[x]>1e18) ft[x]=1e18+1;
x+=x&-x;
}
}
long long qry(int x){
long long res=0;
while (x>0){
res+=ft[x];
if (res>1e18) res=1e18+1;
x-=x&-x;
}
return res;
}
int lol(vector<int> arr){
n=arr.size();
long long res=1;
for (int i=1;i<=n;i++) ft[i]=0;
for (auto i:arr){
long long cur=qry(i+1)+1;
upd(i+1,cur);
res+=cur;
}
//cout<<"try ";
//for (auto i:arr) cout<<i<<' ';
//cout<<res<<'\n';
return res;
}
vector<int> construct_permutation(long long k){
num[0]=1;
for (int i=1;i<63;i++){
num[i]=num[i-1]*2;
}
vector<int> ans;
for (int whack=0;whack<1;whack++){
vector<int> arr;
for (int i=0;i<whack;i++) arr.pb(i);
do{
vector<int> res;
for (auto i:arr) res.pb(i);
if (k-lol(res)<0) continue;
while (lol(res)<k){
vector<int> temp=res;
int id[temp.size()];
for (int i=0;i<(int) temp.size();i++){
id[temp[i]]=i;
temp[i]++;
}
temp.pb(0);
for (int i=1;i<=(int) res.size();i++){
temp[id[i-1]]--;
temp.pop_back();
temp.pb(i);
if (lol(temp)>k){
temp[id[i-1]]++;
temp.back()--;
break;
}
}
res=temp;
}
if (ans.empty() || ans.size()>res.size()){
ans=res;
}
} while (next_permutation(arr.begin(),arr.end()));
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
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 |
5 ms |
212 KB |
Output is correct |
| 4 |
Execution timed out |
1099 ms |
340 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
