Submission #1204788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204788		tapilyoca	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	88 ms	134984 KiB

shoes

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

template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using pll = pair<ll,ll>;
#define pb push_back
#define dbg(x) cerr << #x << ": " << x << endl;

void bruh(queue<ll> q) {
    while(!q.empty()) {
        cerr << q.front() << " ";
        q.pop();
    }
}

ll conv(ll x) {
    if(x < 0) return -x + 100000;
    return x;
}

class comp {
    public:
        bool operator()(pll a, pll b) {
            return a.first + a.second > b.first + b.second;
        }
};

long long count_swaps(std::vector<int> s) {
    ll n = s.size()>>1;
    ll out = 0;

    priority_queue<pll, vec<pll>, comp> pq;
    vec<queue<ll>> dists(200001);

    
    for(ll j = 0; j < 2 * n; j++) {
        ll shoe = conv(s[j]);
        if(s[j] < 0) {
            dists[shoe].push(j);
        } else {
            dists[shoe].push(max(0ll,j-1));
        }
    }

    // cerr << "shmistances: " << endl;
    // for(int i = 0; i <= n; i++) {
    //     if(!dists[i].empty()) {
    //         cerr << " " << i << ": ";
    //         bruh(dists[i]);
    //         cerr << endl;
    //         cerr << -i << ": ";
    //         bruh(dists[i+100000]);
    //         cerr << endl;
    //     }
    // }


    for(int i = 0; i <= n; i++) {
        while(!dists[i].empty()) {
            pq.push({dists[i].front(), dists[i+100000].front()});
            dists[i].pop();
            dists[i+100000].pop();            
        }
    }

    ll mult = 0;
    while(!pq.empty()) {
        pll temp = pq.top();
        pq.pop();
        ll x = temp.first - mult;
        ll y = temp.second - mult;

        // cerr << "(x,y) = " << x << " " << y << endl;
        
        if(y < 0) y = 1; // not sure why this works it just does
        if(x < 0) x = 0;
        
        out += x+y;

        mult += 2;
    }

    return out;
}



/*

4
2 -2 3 -3 2 -2 3 -3
output: 4

*/

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