Submission #1067901

#TimeUsernameProblemLanguageResultExecution timeMemory
1067901LittleOrangeArranging Shoes (IOI19_shoes)C++17
65 / 100
35 ms5208 KiB
#include "shoes.h" #include<bits/stdc++.h> using namespace std; using ll = long long; struct BIT{ ll n; vector<ll> a; BIT(ll N):n(N),a(N+1,0){} void add(ll i, ll v){ for(;i<=n;i+=i&-i) a[i] += v; } ll get(ll i){ ll x = 0; for(;i>0;i-=i&-i) x += a[i]; return x; } }; ll invc(const vector<ll>& v){ ll n = v.size(); BIT t(n); ll r = 0; for(ll i = 0;i<n;i++){ r += i-t.get(v[i]+1); t.add(v[i]+1,1); } return r; } long long count_swaps(std::vector<int> s) { ll n = s.size()/2; if (n<=8){ ll ans = n*n*10; vector<pair<ll,ll>> a; for(ll i = 0;i<n*2;i++){ if (s[i]<0) a.push_back({i,s[i]}); } vector<ll> u(n*2,0); for(auto &o : a){ for(ll i = 0;i<n*2;i++){ if (!u[i]&&s[i]==-o.second){ o.second = i; u[i] = 1; break; } } //cerr << o.first << " " << o.second << "\n"; } do{ vector<ll> p; for(auto &o : a){ p.push_back(o.first); p.push_back(o.second); } ans = min(ans,invc(p)); }while(next_permutation(a.begin(),a.end())); return ans; } vector<ll> to(n*2); ll il = 0, ir = 1; for(ll i = 0;i<n*2;i++){ if (s[i]<0){ to[i] = il; il+=2; }else { to[i] = ir; ir+=2; } } return invc(to); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...