Submission #861424

#	Time	Username	Problem	Language	Result	Execution time	Memory
861424		Unforgettablepl	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	407 ms	30104 KiB

shoes

/*
ID: samikgo1
TASK: wormhole
LANG: C++
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
//#define f first
//#define s second
//#define x first
//#define y second
const int INF = 1e9;
const ll modulo = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>

#define int ll

int arr[200001];

int64_t count_swaps(std::vector<int32_t> s) {
    int n = s.size();
    for(int i=1;i<=n;i++)arr[i]=s[i-1];
    set<pair<int,int>> pairLookup;
    ordered_set currActive;
    for(int i=1;i<=n;i++)pairLookup.emplace(arr[i],i);
    for(int i=1;i<=n;i++)currActive.insert(i);
    int ans = 0;
    for(int i=0;i<n/2;i++){
        auto curr_first = *currActive.find_by_order(0);
        currActive.erase(currActive.find_by_order(0));
        pairLookup.erase(make_pair(arr[curr_first],curr_first));
        if(arr[curr_first]>0)ans++;
        auto curr_second = pairLookup.lower_bound(make_pair(-arr[curr_first],0))->second;
        pairLookup.erase(make_pair(arr[curr_second],curr_second));
        ans+=currActive.order_of_key(curr_second);
        currActive.erase(curr_second);
    }
    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