Submission #501153

#	Time	Username	Problem	Language	Result	Execution time	Memory
501153		LucaIlie	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	275 ms	275976 KiB

shoes

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include "shoes.h"

#define MAX_N 200000

using namespace std;

struct shoe_pair {
    int left, right;

    bool operator < (const shoe_pair &a) const {
        return left + right < a.left + a.right;
    }
};

struct aib {
    long long aib[MAX_N + 1];

    void update( int i, int x ) {
        while ( i <= MAX_N ) {
            aib[i] += x;
            i += (i & -i);
        }
    }

    int query( int i ) {
        int s;

        s = 0;
        while ( i > 0 ) {
            s += aib[i];
            i -= (i & -i);
        }

        return s;
    }
};

int p[2 * MAX_N + 1];
queue <int> q[2 * MAX_N + 2];
shoe_pair pairs[MAX_N];
aib change;

long long count_swaps( vector <int> s ) {
    int n, nrPairs, i;
    long long nrSwaps;

    n = s.size() / 2;

    nrPairs = 0;
    for ( i = 0; i < 2 * n; i++ ) {
        if ( q[-s[i] + n].size() > 0 ) {
            if ( s[i] < 0 )
                pairs[nrPairs] = { i, q[-s[i] + n].front() };
            else
                pairs[nrPairs] = { q[-s[i] + n].front(), i };
            nrPairs++;
            q[-s[i] + n].pop();
        } else
            q[s[i] + n].push( i );
    }

    sort( pairs, pairs + n );

    for ( i = 0; i < n; i++ ) {
        pairs[i].left++;
        pairs[i].right++;
        p[pairs[i].left] = i;
        p[pairs[i].right] = i;
    }

    nrSwaps = 0;
    for ( i = 0; i < n; i++ ) {
        nrSwaps += pairs[i].left + 2 * i - change.query( pairs[i].left ) - (2 * i + 1);
        change.update( pairs[i].left, 1 );
        nrSwaps += pairs[i].right + 2 * i + 1 - change.query( pairs[i].right ) - (2 * i + 2);
        change.update( pairs[i].right, 1 );
    }

    return nrSwaps;
}

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