제출 #1268837

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

shoes

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

struct BIT {
    int n; vector<int> f;
    BIT(int n=0): n(n), f(n+1,0) {}
    void add(int i,int v){ for(; i<=n; i+=i&-i) f[i]+=v; }
    int sum(int i){ int s=0; for(; i>0; i-=i&-i) s+=f[i]; return s; }
};

int64 count_swaps(vector<int> S){
    const int N = (int)S.size();
    // group by absolute size: store (value, index)
    unordered_map<int, vector<pair<int,int>>> by;
    by.reserve(N*2);
    for (int i=0;i<N;i++) by[abs(S[i])].push_back({S[i], i});

    // build pairs (l, r) with l<r; add +1 to answer when right shoe is left of left shoe
    vector<pair<int,int>> pairs; pairs.reserve(N/2);
    int64 ans = 0;
    for (auto &kv : by){
        auto &v = kv.second;
        // sort by value: all negatives (-x = left shoes) come before positives (+x = right shoes)
        sort(v.begin(), v.end());              // (-x, idx)...(+x, idx) for this size
        int k = (int)v.size()/2;
        for (int j=0;j<k;j++){
            int l = v[j].second;               // j-th left
            int r = v[j+k].second;             // j-th right
            if (l > r){ swap(l, r); ++ans; }   // extra 1 if right appears before left
            pairs.emplace_back(l+1, r+1);      // BIT is 1-based
        }
    }

    // process pairs left->right, summing remaining elements between l and r
    sort(pairs.begin(), pairs.end());
    BIT bit(N);
    for (int i=1;i<=N;i++) bit.add(i, 1);      // everyone present
    for (auto &pr : pairs){
        int l = pr.first, r = pr.second;
        ans += bit.sum(r-1) - bit.sum(l);      // strictly between l and r
        bit.add(l, -1); bit.add(r, -1);        // remove endpoints
    }
    return ans;
}

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