제출 #1068001

#제출 시각아이디문제언어결과실행 시간메모리
1068001LittleOrangeArranging Shoes (IOI19_shoes)C++17
10 / 100
1 ms440 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);*/ map<ll,ll> mp; vector<pair<ll,ll>> v; for(ll i = 0;i<n*2;i++){ if (mp.count(-s[i])){ v.push_back({mp[-s[i]],i}); mp.erase(-s[i]); }else{ mp[s[i]] = i; } } sort(v.begin(),v.end()); vector<ll> to; for(auto &o : v){ if (s[o.first]>0){ swap(o.first,o.second); } to.push_back(o.first); to.push_back(o.second); } 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...