제출 #159192

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

shoes

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

long long n,to[200050],pairs=0,br=0;
queue <long long> found[200050];
long long from[200050],perm[200050];

long long count_swaps(vector <int> shoes)
{
    long long i,j;
    n=shoes.size()/2;
    for(i=0;i<2*n;i++)perm[i]=i;
    for(i=0;i<2*n;i++)
    {
        if(shoes[i]<0)
        {
            if(found[shoes[i]+n].empty()==false)
            {
                to[i]=found[shoes[i]+n].front();
                found[shoes[i]+n].pop();
            }
            else
            {
                to[i]=pairs;
                found[n-shoes[i]].push(pairs+1);
                pairs+=2;
            }
        }
        
        else
        {
            if(found[shoes[i]+n].empty()==false)
            {
                to[i]=found[shoes[i]+n].front();
                found[shoes[i]+n].pop();
            }
            else
            {
                to[i]=pairs+1;
                found[n-shoes[i]].push(pairs);
                pairs+=2;
            }
        }
    }
    
    for(i=0;i<2*n;i++)from[to[i]]=i;
    
    //for(i=0;i<2*n;i++)cout<<to[i]<<' ';cout<<endl;
    //for(i=0;i<2*n;i++)cout<<from[i]<<' ';cout<<endl;
    
    for(i=0;i<2*n;i++)
    {
        for(j=0;j<from[i];j++)
        {
            perm[j]++;
        }
        br+=abs(i-perm[from[i]]);
    }
    return br;
}

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