Submission #151392

#	Time	Username	Problem	Language	Result	Execution time	Memory
151392		alexandra_udristoiu	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	217 ms	140336 KiB

shoes

#include "shoes.h"
#include<iostream>
#include<vector>
#include<queue>
#define DIM 100005
using namespace std;
static int n;
static int v[2 * DIM], aib[2 * DIM], ff[2 * DIM];
static queue<int> st[DIM], dr[DIM];
static void update(int x, int val){
    for(; x <= n; x += (x & -x) ){
        aib[x] += val;
    }
}
static int query(int x){
    int sum = 0;
    for(; x >= 1; x -= (x & -x) ){
        sum += aib[x];
    }
    return sum;
}
long long count_swaps(vector<int> s) {
    int i;
    long long sol = 0;
    n = s.size();
    for(i = 1; i <= n; i++){
        v[i] = s[i - 1];
        update(i, 1);
    }
    for(i = n; i >= 1; i--){
        if(v[i] < 0){
            if( !dr[ -v[i] ].empty() ){
                ff[i] = dr[ -v[i] ].front();
                dr[ -v[i] ].pop();
            }
            else{
                st[ -v[i] ].push(i);
            }
        }
        else{
            if( !st[ v[i] ].empty() ){
                ff[i] = st[ v[i] ].front();
                st[ v[i] ].pop();
            }
            else{
                dr[ v[i] ].push(i);
            }
        }
    }
    for(i = 1; i <= n; i++){
        if(ff[i] != 0){
            sol += query(ff[i]) - query(i) - 1;
            if(v[i] > 0){
                sol++;
            }
            update(ff[i], -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