제출 #1364868

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364868		nini_gvenetadze	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	94 ms	138156 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

int ft[200067];

int sum(int i) {
    int s=0;
    for (; i>=0; i =(i&(i+1))-1)
        s+=ft[i];
    return s;
}

void add(int i, int v) {
    for (; i<200067; i=i | (i + 1))
        ft[i]+=v;
}
 long long count_swaps(vector<int> a)
 {
    int n=(int)(a.size())/2;

    vector<queue<int>> pos(2*n +1);
    for(int i=0; i<2*n; i++)
    {
        pos[a[i]+n].push(i);
    }

    vector<bool> vec(2*n);
    long long ans=0;

    for(int i=0; i<2*n; i++)
    {
        if(vec[i]) continue;

        int j=pos[-a[i]+n].front();
        pos[-a[i]+n].pop();
        pos[a[i]+n].pop();

        vec[j]=1;

        ans+=j-i-1;

        if(a[i]>0) ans++;
        ans-=sum(j)-sum(i);
        add(j, 1);
    }
    return ans;
 }

• 서브태스크 1: 10 / 10
• 서브태스크 2: 20 / 20
• 서브태스크 3: 20 / 20
• 서브태스크 4: 15 / 15
• 서브태스크 5: 20 / 20
• 서브태스크 6: 15 / 15