제출 #1030428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1030428		AlgorithmWarrior	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	290 ms	273740 KiB

shoes

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

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: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15