Submission #677984

#	Time	Username	Problem	Language	Result	Execution time	Memory
677984		kderylo	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	318 ms	360248 KiB

shoes

#include <iostream>
#include <vector>
#include <deque>
#include "shoes.h"
using namespace std;
const int stala=262144;
deque<int>k_dodatnie[stala];
deque<int>k_ujemne[stala];
int docelowy[stala];
long long tree[2*stala];
bool o[stala];
void update(int index)
{
    index+=stala-1;
    tree[index]=1;
    while(index>1){
        index/=2;
        tree[index]=tree[2*index]+tree[(2*index)+1];
    }
}
long long query(int index,int index2)
{
    index+=stala-1;
    index2+=stala-1;
    long long suma=tree[index];
    if(index!=index2){
        suma+=tree[index2];
    }
    while(index/2!=index2/2){
        if(index%2==0){
            suma+=tree[index+1];
        }
        if(index2%2==1){
            suma+=tree[index2-1];
        }
        index/=2;
        index2/=2;
    }
    return suma;
}
long long count_swaps(vector<int>wektor)
{
    int ile=(int)wektor.size();
    long long wyn=0;
    for(int i=0;i<(int)wektor.size();i++){
        int x=wektor[i];
        if(x>0){
            if(k_ujemne[x].empty()){
                k_dodatnie[x].push_back(i);
            }
            else{
                docelowy[k_ujemne[x].front()+1]=i+1;
                k_ujemne[x].pop_front();
            }
        }
        else{
            x*=(-1);
            if(k_dodatnie[x].empty()){
                k_ujemne[x].push_back(i);
            }
            else{
                docelowy[k_dodatnie[x].front()+1]=i+1;
                k_dodatnie[x].pop_front();
                wyn++;
            }
        }
    }
    for(int i=1;i<=ile;i++){
        if(o[i]==0){
            o[i]=1;
            o[docelowy[i]]=1;
            long long ile_odjac=query(i,docelowy[i]);
            wyn+=(long long)docelowy[i]-(long long)i-1-ile_odjac;
            update(i);
            update(docelowy[i]);
        }
    }
    return wyn;
}

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