Submission #741177

#	Time	Username	Problem	Language	Result	Execution time	Memory
741177		JakobZorz	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1090 ms	22612 KiB

shoes

#include "shoes.h"
#include <set>
using namespace std;
#define ll long long

set<int> shoes[200000];
int n;
int dist[200000];

ll get_dist(int idx){
    ll d=0;
    for(int i=0;i<idx;i++)
        d+=dist[i];
    return d;
}

ll count_swaps(vector<int> s) {
    n = s.size();
    for(int i=0;i<n;i++)
        shoes[s[i]+100000].insert(i);
    for(int i=0;i<n;i++)
        dist[i]=1;
    ll res=0;
    int pos1=0;
    while(pos1<n){
        int pos2=*shoes[100000-s[pos1]].begin();
        
        res+=get_dist(pos2);
        if(s[pos1]<0)
            res--;
        dist[pos1]=0;
        dist[pos2]=0;
        shoes[100000-s[pos1]].erase(shoes[100000-s[pos1]].begin());
        shoes[100000+s[pos1]].erase(shoes[100000+s[pos1]].begin());
        
        while(dist[pos1]==0) pos1++;
    }
    
    return res;
}

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