제출 #500868

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500868		Khizri	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1098 ms	332 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"OK"<<endl;
const int mxn=1e6+1000;
int color[mxn],n,tree[mxn];
int query(int ind){
    int ans=0;
    while(ind>0){
        ans+=tree[ind];
        ind-=(ind&(-ind));
    }
    return ans;
}
void update(int ind,int val){
    while(ind<=n){
        tree[ind]+=val;
        ind+=(ind&(-ind));
    }
}
bool f(pii a,pii b){
    return a.F+a.S<b.F+b.S;
}
ll funk(vector<pii>&vt){
    ll ans=0;
    sort(all(vt),f);
    for(int i=0;i<n/2;i++){
        int x=vt[i].F+query(vt[i].F);
        ans+=abs(x-1);
        update(vt[i].F,-1);
        int y=vt[i].S+query(vt[i].S);
        ans+=abs(y-1);
        update(vt[i].S,-1);
    }
    return ans;
}
long long count_swaps(vector<int> s) {
    n=s.size();
    map<int,int>mp;
	vector<pii>vt;
	for(int i=0;i<n;i++){
        if(color[i]) continue;
        if(mp[-s[i]]>0){
            int x=mp[-s[i]];
            mp[-s[i]]=0;
            if(s[i]<0){
                vt.pb({i+1,x});
            }
            else{
                vt.pb({x,i+1});
            }
            color[i]=1;
            color[x-1]=1;
        }
        else{
            mp[s[i]]=i+1;
        }
	}
    ll ans=funk(vt);
    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15