제출 #1150922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150922		danglayloi1	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	48 ms	19016 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=2e5+5;
int v[nx];
void add(int x)
{
    for(; x <= 200000; x+=x&-x)
        v[x]++;
}
int get(int x)
{
    int res=0;
    for(; x > 0; x-=x&-x)
        res+=v[x];
    return res;
}
vector<int> l[nx], r[nx];
ii f[nx];
bool cmp(ii a, ii b)
{
    return min(a.fi, a.se)<min(b.fi, b.se);
}
ll count_swaps(vector<int> a)
{
    ll ans=0;
    int n=a.size();
    for(int i = 0; i < n; i++)
        if(a[i]<0) l[-a[i]].emplace_back(i);
        else r[a[i]].emplace_back(i);
    int m=0;
    for(int i = 1; i <= n/2; i++)
        for(int j = 0; j < l[i].size(); j++)
            f[++m]={l[i][j], r[i][j]};
    sort(f+1, f+m+1, cmp);
    for(int i = 1; i <= m; i++)
    {
        int pos=f[i].fi+1+get(n)-get(f[i].fi);
        ans+=(pos-i*2+1);
        add(f[i].fi+1);
        pos=f[i].se+1+get(n)-get(f[i].se);
        ans+=(pos-i*2);
        add(f[i].se+1);
    }
    return ans;
}
// int main()
// {
//     cout<<count_swaps({-2, 2, 2, -2, -2, 2});
// }

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