Submission #349414

#TimeUsernameProblemLanguageResultExecution timeMemory
349414Sho10Cheerleaders (info1cup20_cheerleaders)C++17
5 / 100
2075 ms30148 KiB
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10 #define ll long long #define double long double #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #define aint(a) (a).begin(), (a).end() #define f first #define s second #define pb push_back #define mp make_pair #define pi pair #define rc(s) return cout<<s,0 #define endl '\n' #define mod 1000000007 #define PI 3.14159265359 #define MAXN 100005 #define INF 1000000005 #define LINF 1000000000000000005ll #define CODE_START ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; ll n,mn=LINF,res=LINF; vector<ll>ans; vector<ll>a; map<vector<ll>,ll>viz; void solve(ll step,ll x){ vector<ll>st; st=a; if(step==1){ for(ll i=0;i<n/2;i++) { swap(a[i],a[n/2+i]); } if(viz[a]==1){ a=st; return; } }else if(step==2){ vector<ll>nw; for(ll i=0;i<n;i++) { if(i%2==0){ nw.pb(a[i]); } } for(ll i=0;i<n;i++) { if(i%2){ nw.pb(a[i]); } } a=nw; if(viz[a]==1){ a=st; return; } } ll inv=0; for(ll i=0;i<n;i++) { for(ll j=i+1;j<n;j++) { if(a[j]<a[i]){ inv++; } } } if(inv<mn){ mn=inv; res=x; }else if(inv==mn){ res=min(res,x); } viz[a]=1; solve(1,x+1); solve(2,x+1); a=st; return; } int32_t main(){ CODE_START; cin>>n; n=(1<<n); for(ll i=1;i<=n;i++) { ll x; cin>>x; a.pb(x); } viz[a]=1; solve(1,1); solve(2,1); cout<<mn<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...