Submission #297409

#	Time	Username	Problem	Language	Result	Execution time	Memory
297409		shayan_p	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	38 ms	2048 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e5 + 10;

int cnt[maxn];
ll sum, sumabs;

void add(int pos, int x){
    sum-= cnt[pos];
    sumabs-= abs(cnt[pos]);
    cnt[pos]+= x;
    sum+= cnt[pos];
    sumabs+= abs(cnt[pos]);
}

ll count_swaps(vector<int> a){
    ll ans = 0;
    for(int x : a){
	if(x < 0){
	    add(cnt[-x], -1);
	}
	else{
	    add(cnt[x], 1);
	}
	ans+= sumabs;
	if(sum & 1){
	    if(sum == sumabs)
		ans++;
	    else
		ans--;
	}
    }
    return ans / 2;
}

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