Submission #1236418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236418		mariza	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	1101 ms	142012 KiB

shoes

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

typedef long long ll;
#define MID ((l+r)/2)

long long count_swaps(vector<int> s){
    ll n=s.size()/2;

    queue<ll> l[n+1], r[n+1];
    ll c=0;
    for(ll i=0; i<2*n; i++){
        if(s[i]<0){
            l[-s[i]].push(2*c);
            r[-s[i]].push(2*c+1);
            // cout<<-s[i]<<" "<<2*i<<endl;
            c++;
        }
    }
    // cout<<"ok1"<<endl;

    vector<ll> s2;
    ll pos[2*n];
    for(ll i=0; i<2*n; i++){
        if(s[i]<0){
            s2.push_back(l[-s[i]].front());
            pos[l[-s[i]].front()]=s2.size()-1;
            l[-s[i]].pop();
        }
        else{
            s2.push_back(r[s[i]].front());
            pos[r[s[i]].front()]=s2.size()-1;
            r[s[i]].pop();
        }
    }
    // cout<<"ok2"<<endl;

    ll ans=0;
    for(ll i=0; i<2*n; i++){
        for(ll j=0; j<i; j++){
            if(s2[j]>s2[i]) ans++;
        }
    }
    
    return ans;
}

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