Submission #1227333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227333		hengliao	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1096 ms	20548 KiB

shoes

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

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef long long ll;

namespace{
    const ll mxN=2e5+5;

    ll n;

    vll v[mxN][2];

    ll a[mxN];
    ll p[mxN];
}

long long count_swaps(vector<int> s) {
	n=s.size();
    for(ll i=0;i<n;i++){
        if(s[i]<0){
            v[abs(s[i])][0].pb(i);
        }
        else{
            v[s[i]][1].pb(i);
        }
    }
    for(ll i=1;i<=n/2;i++){
        for(ll j=0;j<(ll) v[i][0].size();j++){
            p[v[i][0][j]]=v[i][1][j];
            p[v[i][1][j]]=v[i][0][j];
        }
    }
    memset(a, -1, sizeof(a));
    ll timer=0;
    for(ll i=0;i<n;i++){
        if(a[i]==-1){
            if(s[i]<0){
                a[i]=timer;
                a[p[i]]=timer+1;
            }
            else{
                a[i]=timer+1;
                a[p[i]]=timer;
            }
            timer+=2;
        }
    }
    ll ans=0;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<i;j++){
            if(a[j]>a[i]) ans++;
        }
    }
    return ans;
}

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