Submission #184045

#	Time	Username	Problem	Language	Result	Execution time	Memory
184045		Ruxandra985	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	297 ms	140272 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define DIMN 200010
using namespace std;
int aib[DIMN] , f[DIMN];
deque <int> poz[DIMN];
void update (int i , int n , int x){

    for (;i<=n;i = i + (i & (-i)))
        aib[i]+=x;

}
int query (int i){
    int sol = 0;

    for (;i;i = i - (i & (-i)))
        sol+=aib[i];
    return sol;

}
long long count_swaps (vector <int> v){
    int n , i , p1 , p2 , aux;
    long long sol=0;
    n = v.size() / 2;

    for (i=0;i<2*n;i++){
        poz[max(v[i] , -v[i])].push_back(i); /// a doua pozitie
    }

    for (i=0;i<2*n;i++){
        if (!f[i]){ /// nu ai mai intalnit
            p1 = i + query(i + 1);
            p2 = poz[max(v[i] , -v[i])].front();
            poz[max(v[i] , -v[i])].pop_front();
            while (p2 <= i || v[p2] == v[i]){
                p2 = poz[max(v[i] , -v[i])].front();
                poz[max(v[i] , -v[i])].pop_front();
            }
            f[p2] = 1;
            aux = p2;
            p2 += query(p2 + 1);
            sol = sol + (p2 - p1 - 1);
            if (v[i] > 0)
                sol++; /// mai faci un swap
            update (i + 1, 2*n , 1);
            update (aux+1 , 2*n , -1);
        }
    }
    return sol;

}

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