Submission #1030418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030418		AlgorithmWarrior	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	180 ms	278516 KiB

shoes

#include "shoes.h"
#include <cstdio>
#include <cassert>
#include <vector>
#include <deque>
#include <cmath>
#define MAX 100005

using namespace std;

int aib[MAX];

int ub(int x)
{
    return x&(-x);
}

void add(int poz)
{
    for(;poz<MAX;poz+=ub(poz))
        ++aib[poz];
}

int sum(int poz)
{
    int s=0;
    for(;poz;poz-=ub(poz))
        s+=aib[poz];
    return s;
}

deque<int>left[MAX];
deque<int>right[MAX];

long long count_swaps(vector<int> s) {
    int ind=0;
    long long rasp=0;
    for(auto i : s)
    {
        ++ind;
        if(i<0)
            left[-i].push_back(ind);
        else
            right[i].push_back(ind);
        int abss=abs(i);
        if(!left[abss].empty() && !right[abss].empty())
        {
            int indd=left[abss].front();
            left[abss].pop_front();
            rasp+=indd-1-sum(indd-1);
            add(indd);
            indd=right[abss].front();
            right[abss].pop_front();
            rasp+=indd-1-sum(indd-1);
            add(indd);
        }
    }
    return rasp;
}

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