# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
983516 | 2024-05-15T15:27:15 Z | Faisal_Saqib | Permutation (APIO22_perm) | C++17 | 110 ms | 596 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define vll vector<int> vector<int> cp(ll k)// O(lg n) { vector<int> ans; ll n_req=0; ll hb=-1; for(int j=59;j>=0;j--) { ll pw=(1ll<<j); if(k&pw) { if(hb==-1) { n_req+=j; hb=j; } else n_req++; } } ll last=n_req-1; int first=0; // cout<<last<<endl; for(int l=0;l<60 and l<hb;l++) { if(k&(1ll<<l)) { ans.push_back(first); first++; } if(first<=last) { ans.push_back(last); last--; } } reverse(begin(ans),end(ans)); return ans; } ll task(ll n) // O(lg n) { ll cp=0; for(int bit=59;bit>=0;bit--) { if(n&(1ll<<bit)) { cp+=bit; n^=(1ll<<bit); break; } } while(n) { cp++; n-=(n&-n); } return cp; } int cpp(ll k) { ll mx=task(k); ll a=-1; ll b=k; ll SQ=5e2; SQ=min(SQ,k-1); for(ll d=2;d<=SQ;d++) { if(k%d==0) { ll f=task(d); ll s=task(k/d); if((f+s)<mx) { mx=f+s; a=d; b=k/d; } } } return mx; } vector<int> cpp_c(ll k) { ll mx=task(k); ll a=-1; ll b=k; ll SQ=5e2; SQ=min(SQ,k-1); for(ll d=2;d<=SQ;d++) { if(k%d==0) { ll f=task(d); ll s=task(k/d); if((f+s)<mx) { mx=f+s; a=d; b=k/d; } } } if(a==-1) { return cp(k); } else{ vll ap=cp(a); vll bp=cp(b); ll nm=ap.size(); for(auto i:bp) ap.pb(i+nm); return ap; } return {}; } vector<int> construct_permutation(ll k) { ll mx=task(k); ll a=-1; ll b=k; ll SQ=5e2; SQ=min(SQ,k-1); for(ll d=2;d<=SQ;d++) { if(k%d==0) { ll f=cpp(d); ll s=cpp(k/d); if((f+s)<mx) { mx=f+s; a=d; b=k/d; } } } if(a==-1) { return cp(k); } else{ vll ap=cpp_c(a); vll bp=cpp_c(b); ll nm=ap.size(); for(auto i:bp) ap.pb(i+nm); return ap; } return {}; } // int main() // { // int n; // cin>>n; // auto tp= construct_permutation(n); // for(auto k:tp) // { // cout<<k<<' '; // } // cout<<endl; // }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 3 ms | 348 KB | Output is correct |
4 | Correct | 2 ms | 348 KB | Output is correct |
5 | Partially correct | 4 ms | 440 KB | Partially correct |
6 | Correct | 5 ms | 344 KB | Output is correct |
7 | Correct | 5 ms | 348 KB | Output is correct |
8 | Partially correct | 5 ms | 348 KB | Partially correct |
9 | Correct | 5 ms | 456 KB | Output is correct |
10 | Partially correct | 6 ms | 596 KB | Partially correct |
11 | Partially correct | 2 ms | 348 KB | Partially correct |
12 | Correct | 110 ms | 444 KB | Output is correct |
13 | Correct | 19 ms | 592 KB | Output is correct |