제출 #519651

#제출 시각아이디문제언어결과실행 시간메모리
519651CasperWongArranging Shoes (IOI19_shoes)C++14
50 / 100
1063 ms139548 KiB
#include<bits/stdc++.h> using namespace std; long long count_swaps(vector<int>s){ long long n=s.size()/2,ans=0; queue<long long>pr[2*n+100]; vector<long long>vec={}; for(int i=-n;i<=n;i++) while(pr[i+n].size()) pr[i+n].pop(); for(int i=0;i<2*n;i++) pr[s[i]+n].push(i); for(int i=0;i<2*n;i++){ if(!s[i]) continue; if(s[i]>0) ans++; vec.push_back(pr[-s[i]+n].front()); s[pr[-s[i]+n].front()]=0; sort(vec.begin(),vec.end()); reverse(vec.begin(),vec.end()); while(vec.back()<=i) vec.pop_back(); for(auto j:vec) if((j>i)&&(j<pr[-s[i]+n].front())) ans--; ans+=abs(pr[-s[i]+n].front()-i)-1; pr[s[i]+n].pop(); pr[-s[i]+n].pop(); if(s[i]==-s[i+1]) i++; // cerr<<ans<<endl; } return ans; }
#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...