Submission #1212453

#TimeUsernameProblemLanguageResultExecution timeMemory
1212453loiiii12358Arranging Shoes (IOI19_shoes)C++20
50 / 100
1096 ms2632 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; long long count_swaps(vector<int> s) { long long n=s.size()/2,ans=0; vector<int> l(n+1),r(n+1); pair<int,int> best; // set<pair<int,int>> S; // for(int i=0;i<2*n;i++){ // S.insert({s[i],i}); // } for(int i=0;i<n;i++){ fill(l.begin(),l.end(),1e9); fill(r.begin(),r.end(),1e9); for(int j=2*i;j<2*n;j++){ if(s[j]<0){ l[-s[j]]=min(l[-s[j]],j-2*i); }else{ r[s[j]]=min(r[s[j]],j-2*i); } } best={1e9,1e9}; for(int j=1;j<=n;j++){ if(l[j]<r[j]){ r[j]--; } if(l[j]+r[j]<best.first){ best={l[j]+r[j],j}; } } for(int j=2*i;j<2*n;j++){ if(-s[j]==best.second){ for(int k=j-1;k>=2*i;k--){ swap(s[k],s[k+1]); ans++; } break; } } for(int j=2*i+1;j<2*n;j++){ if(s[j]==best.second){ for(int k=j-1;k>=2*i+1;k--){ swap(s[k],s[k+1]); ans++; } break; } } } 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...