Submission #305408

#	Time	Username	Problem	Language	Result	Execution time	Memory
305408		knon0501	Arranging Shoes (IOI19_shoes)	C++14	30 / 100	36 ms	7416 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int c[1005];
queue<int> a[1005],b[1005];
long long count_swaps(std::vector<int> s) {
    int i,j;
    long long ans=0;
    int n=s.size();

    for(i=0 ; i<n ; i++){
        if(s[i]>0)
            a[s[i]].push(i);
        else
            b[-s[i]].push(i);
    }

    for(i=0 ; i<n ; i+=2){
        int k=0;
        int t=1e9;
        for(j=1 ; j*2<=n ; j++){
            if(!a[j].empty()){
                int x=a[j].front();
                int y=b[j].front();
                int xx=x-i+c[x];
                int yy=y-i+c[y]-(x>y);
                if(xx+yy<t){
                    t=xx+yy;
                    k=j;
                }
            }
        }
        for(j=a[k].front() ; j>=0 ; j--)c[j]++;
        for(j=b[k].front() ; j>=0 ; j--)c[j]++;
        a[k].pop();
        b[k].pop();
        ans+=t;

    }
    return ans;
}

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