Submission #151385

#	Time	Username	Problem	Language	Result	Execution time	Memory
151385		alexandra_udristoiu	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	3 ms	380 KiB

shoes

#include "shoes.h"
#include<iostream>
#include<vector>
#define DIM 200005
using namespace std;
static int n;
static int v[DIM], aib[DIM], st[DIM], dr[DIM], ff[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){
            ff[i] = dr[ -v[i] ];
            dr[ -v[i] ] = 0;
            if(ff[i] == 0){
                st[ -v[i] ] = i;
            }
        }
        else{
            ff[i] = st[ v[i] ];
            st[ v[i] ] = 0;
            if(ff[i] == 0){
                dr[ v[i] ] = 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: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15