Submission #489917

#	Time	Username	Problem	Language	Result	Execution time	Memory
489917		kevin	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	203 ms	139768 KiB

shoes

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

#define ll long long
#define nl cout<<"\n"
#define ca(v) for(auto i:v) cout<<i<<" ";

struct BIT {
    vector<int> f;
    int n;
    void init(int N) { f = vector<int>(N+1, 0); n = N;}
    int lsb(int x) { return x & -x; }
    void update(int p, int v){ 
        while(p <= n){ f[p] += v; p += lsb(p); } 
    }
    int query(int p) { 
        int sum = 0; 
        while (p > 0) { sum += f[p]; p -= lsb(p); } 
        return sum; 
    }
};

ll count_swaps(vector<int> ar){
    int n = ((int)ar.size()) / 2;
    queue<int> pos[n+1][2];
    vector<int> ord;
    for(int i=0; i<2*n; i++){
        if(ar[i] < 0) {
            pos[-ar[i]][0].push(i+1);
            ord.push_back(-ar[i]);
        }
        else pos[ar[i]][1].push(i+1);
    }
    BIT fen; fen.init(2*n+5);
    ll ans = 0;
    for(int k=1; k<=n; k++){
        int x = ord[k-1];
        int i = pos[x][0].front(); pos[x][0].pop();
        int j = pos[x][1].front(); pos[x][1].pop();
        // cout<<x<<" "<<i<<" "<<j<<"\n";
        ans += (ll) i+fen.query(i) - (2*k-1);
        fen.update(1, 1); fen.update(i, -1);
        // cout<<ans<<" ";
        ans += (ll)j+fen.query(j) - 2*k;
        // cout<<ans<<" ";
        fen.update(1, 1); fen.update(j, -1);
        // nl;
    }
    return ans;
    return 0;
}

// int main()
// {
//     // ios_base::sync_with_stdio(0); cin.tie(0);
//     if (fopen("input.in", "r")) freopen("input.in", "r", stdin);
//     int n; cin>>n;
//     vector<int> ar(2*n);
//     for(int i=0; i<2*n; i++) cin>>ar[i];
//     cout<<count_swaps(ar);
// }

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