Submission #1147664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147664		gulmix	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	41 ms	11452 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define oset tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>

const int MAXN = 200005;

struct bit{
    int tree[MAXN];
    void add(int x, int v){
        for(int i = x; i < MAXN; i += i & -i)tree[i] += v;
    }
    int query(int x){
        int ans = 0;
        for(int i = x; i; i -= i & -i)ans+=tree[i];
        return ans;
    }
}bit;

ll count_swaps(vector<int> a){
    int n = size(a) / 2;
    int tot = 0;
    vector<pair<int, int>> v;
    vector<pair<int, int>> ord[MAXN];
    for(int i = 0; i < a.size(); i++){
        ord[abs(a[i])].emplace_back(a[i], i);
    }
    for(int i = 1; i <= n; i++){
        sort(all(ord[i]));
        for(int j = 0; j < ord[i].size() / 2; j++){
            int l = ord[i][j].second;
            int r = ord[i][j + ord[i].size()/2].second;
            if(l > r){
                swap(l, r);
                tot++;
            }
            v.emplace_back(l + 1, r + 1);
        }
    }
    for(int i = 1; i <= 2*n; i++)bit.add(i, 1);
    sort(all(v));
    for(auto &i: v){
        tot += bit.query(i.second - 1) - bit.query(i.first);
        bit.add(i.first, -1);
        bit.add(i.second, -1);
    }
    return tot;
}

//int main(){
//    ios::sync_with_stdio(false);
//    cin.tie(0);
//    //ifstream cin("cycle2.in");
//    //ofstream cout("cycle2.out");
//    vector<int> b = {15, 17, 16, 18};
//    vector<int> a = find_subset(10, 20, b);
//    for(auto &i: a)cout << i << ' ';
//}

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