# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
953680 | 2024-03-26T12:43:47 Z | De3b0o | Permutation (APIO22_perm) | C++17 | 14 ms | 348 KB |
#include "perm.h" #include<bits/stdc++.h> #define ll long long #define F first #define S second #define in insert #define pb push_back #define ppb pop_back() #define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define cans cout << ans << "\n"; #define yes cout << "Yes" << "\n"; #define no cout << "No" << "\n"; #define pll pair<ll,ll> #define lin cout << "\n"; #define sqr 340 #define mod 1000000007 #define mid ((l+r)/2) //#define lc (2*n) //#define rc (2*n+1) using namespace std; ll fp(ll x , ll y) { if(y==0) return 1; ll z = fp(x,y/2); if(y&1) return z*z*x; else return z*z; } string tb(ll x) { string s = ""; while(x>0) { if(x&1) s+='1'; else s+='0'; x/=2; } while(s.size()<60) s+='0'; return s; } std::vector<int> construct_permutation(long long k) { vector<ll> v; for(int sz = 1 ; 90>=sz ; sz++) { v.clear(); ll x = k-sz-1; string s = tb(x); for(int i = 0 ; sz>i ; i++) { if(s[i]=='1') v.pb(i); else v.pb(0); } ll y = 0; for(int i = 0 ; v.size()>i ; i++) { y+=fp(2,v[i]); } if(y==k-1) break; } ll n = v.size(); vector<int> ans(n,0); map<ll,ll> mp; for(int i = n-1 ; i>=0 ; i--) { ll y; for(int j = 0 ; n>j ; j++) { if(mp[j]==1) continue; ll x = j; for(auto it : mp) { if(it.S==1) { if(it.F<j) x--; } } if(x==v[i]) { y=j; break; } } ans[i]=y; mp[y]=1; } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 4 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 4 ms | 348 KB | Output is correct |
3 | Incorrect | 14 ms | 348 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |