Submission #468676

#	Time	Username	Problem	Language	Result	Execution time	Memory
468676		Apiram	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1100 ms	70448 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
long long count_swaps(std::vector<int> s) {
int n = s.size();
vector<int>arr=s;
vector<deque<int>>neg(1e5);
for (int i  = 0;i<n;++i)
	{	
	if (arr[i]>0){
		neg[arr[i]].push_back(i);
	}
	}
	int64_t ans = 0;
for (int i = 0,cur = 0;i<n;i++){
	if (arr[i]<0){
		int j  = i;
		while(cur!=j){
			swap(arr[j-1],arr[j]);
			if (arr[j]>0){
				for (int k = 0;;++k){
					if (neg[arr[j]][k]==j-1){
						neg[arr[j]][k]++;
						break;
					}
				}
			}
			
			--j;
			ans++;
		}
		++cur;
		j = neg[-arr[cur-1]].front();
		neg[-arr[cur-1]].pop_front();
		while(j!=cur){
			swap(arr[j-1],arr[j]);
			if (arr[j]>0){
				for (int k = 0;;++k){
					if (neg[arr[j]][k]==j-1){
						neg[arr[j]][k]++;
						break;
					}
				}
			}
			--j;
			ans++;
		}
		cur++;
	}
}
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