제출 #168355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
168355		Andrei_Cotor	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	86 ms	15352 KiB

shoes

#include "shoes.h"
//#include<bits/stdc++.h>

using namespace std;

vector<int> St[100005],Dr[100005];
int IndSt[100005],IndDr[100005];
int Viz[100005];
int F[100005];

int query(int poz)
{
    int rez=poz;
    while(poz>0)
    {
        rez+=F[poz];
        poz=poz-(poz&(poz^(poz-1)));
    }
    return rez;
}

void update(int poz, int val)
{
    while(poz<=100000)
    {
        F[poz]+=val;
        poz=poz+(poz&(poz^(poz-1)));
    }
}

long long count_swaps(vector<int> V)
{
    int n=V.size();
    for(int i=0; i<n; i++)
    {
        if(V[i]<0)
            St[-V[i]].push_back(i);
        else
            Dr[V[i]].push_back(i);
    }

    long long rez=0;
    for(int i=0; i<n; i++)
    {
        if(Viz[i])
            continue;
        Viz[i]=1;
        if(V[i]<0)
        {
            IndSt[-V[i]]++;

            int other=Dr[-V[i]][IndDr[-V[i]]];
            Viz[other]=1;
            IndDr[-V[i]]++;

            rez+=1LL*(query(other+1)-query(i+1)-1);
            update(other+1,-1);
            update(i+1+1,1);
        }
        else
        {
            IndDr[V[i]]++;

            int other=St[V[i]][IndSt[V[i]]];
            Viz[other]=1;
            IndSt[V[i]]++;

            rez+=1LL*(query(other+1)-query(i+1));
            update(other+1,-1);
            update(i+1+1,1);
        }
    }
    return rez;
}

/*
int main()
{
    int n;
    cin>>n;
    vector<int> A;
    for(int i=1; i<=n; i++)
    {
        int x;
        cin>>x;
        A.push_back(x);
    }
    cout<<count_swaps(A)<<"\n";
    return 0;
}*/

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