| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1140213 | imarn | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
using namespace std;
const int mxn=2e5+5;
ll fw[mxn]{0};
void add(int i,int amt){
for(;i<mxn;i+=i&-i)fw[i]+=amt;
}
int qr(int i,int rs=0){
for(;i;i-=i&-i)rs+=fw[i];
return rs;
}priority_queue<int,vector<int>,greater<int>>v[mxn],vv[mxn];
priority_queue<pii,vector<pii>,greater<pii>>p1,p2;
long long count_swaps(std::vector<int> s){
int n=s.size();ll ans=0;
for(int i=0;i<n;i++){
if(s[i]>0)v[s[i]].push(i);
if(s[i]<0)vv[-s[i]].push(i);
}
for(int i=1;i<n;i++){
if(v[i].empty())continue;
int x=v[i].top(),y=vv[i].top();
if(x<y)p2.push({abs(x)+abs(y),i});
if(x>y)p1.push({abs(x-1)+abs(y),i});
}
int cnt=n/2;
while(cnt--){
int rs=1e9,mm,ml,mr,md=-1;
if(!p1.empty()){
int i=p1.top().s;
int x=v[i].top(),y=vv[i].top();
int tx=x+qr(x+1);
int ty=y+qr(y+1);
if(rs>abs(tx-1)+abs(ty)){
rs=abs(tx-1)+abs(ty);
mm=i;ml=min(x,y)+1,mr=max(x,y)+2;
md=0;
}
}
else if(!p2.empty()){
int i=p2.top().s;
int x=v[i].top(),y=vv[i].top();
int tx=x+qr(x+1);
int ty=y+qr(y+1);
if(rs>abs(tx)+abs(ty)){
rs=abs(tx)+abs(ty);
mm=i;ml=min(x,y)+1,mr=max(x,y)+2;
md=1;
}
}ans+=rs;v[mm].pop();vv[mm].pop();add(ml,-1);add(mr,-1);
if(!md)p1.pop();
else p2.pop();
}
return ans;
}
int main(){
cout<<count_swaps({2,1,-1,-2});
}