Submission #146672

#	Time	Username	Problem	Language	Result	Execution time	Memory
146672		abacaba	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	2 ms	376 KiB

shoes

#include <cstdio>
#include <cassert>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stack>
#include <map>
#include "shoes.h"
using namespace std;

const int N = 2e5 + 15;
int n, a[N];
map <int, bool> used;
map <int, stack <int> > ord;

long long count_swaps(vector<int> s) {
	n = s.size();
	long long ans = 0;
	for(int i = 0; i < n; ++i)
		a[i + 1] = s[i];
	for(int i = n; i; --i)
		ord[a[i]].push(i);
	for(int i = 1; i < n; ++i) {
		if(ord[a[i]].empty() || ord[a[i]].top() != i)
			continue;
		ord[a[i]].pop();
		int j = ord[-a[i]].top();
		ord[-a[i]].pop();
		if(a[i] < 0)
			ans += j - i - 1;
		else
			ans += j - i;
	}
	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