Submission #1001968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001968		KasymK	Arranging Shoes (IOI19_shoes)	C++17	65 / 100	1049 ms	3260 KiB

shoes

#include "bits/stdc++.h"
using namespace std;
#define ll long long

ll count_swaps(vector<int> v){
    // for subtask 4
    int n = (int)v.size(), ok = 1;
    n /= 2;
    for(int i = 0; i < n; ++i)
        ok &= (v[i] < 0);
    for(int i = 0; i < n; ++i)
        ok &= (-v[i] == v[i+n]);
    // if v[0...n-1] is all left, it means v[n...2*n-1] is all right
    if(ok){
        n--;
        ll answer = n*1ll*(n+1)/2;
        return answer;
    }
    n *= 2;
    ll answer = 0;
    for(int i = 0; i < n-1; i+=2){
        if(-v[i] == v[i+1]){
            // if v[i] and v[i+1] are same size
            if(v[i] > 0){
                // it means if v[i] is right shoes
                answer++;
                swap(v[i], v[i+1]);
            }
        }
        else{
            // is it isn't same size
            int ad = -1;
            for(int j = i+1; j < n; ++j)
                if(v[i] == -v[j]){
                    ad = j;
                    break;
                }
            // we find a pair of that shoes
            for(int j = ad; j > i+1; --j){
                answer++;
                swap(v[j], v[j-1]);
            }
            if(v[i] > 0){
                answer++;
                swap(v[i], v[i+1]);
                // it means v[i] is right shoes
            }
        }
    }
    return answer;
}

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