Submission #1343722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1343722		ElyesChaabouni	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1095 ms	1960 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define ll long long
#define endl "\n"
using namespace std;

long long count_swaps(vector<int> s){
	int N = s.size()/2;
	ll res = 0;
	
	auto make_swap= [&](int l,int r){
		assert(l<=r);
		while(l<r){
			swap(s[r],s[r-1]);
			r--;
		}
	};

	for(int i=0;i<2*N;i+=2){
		if(s[i]<0){
			int idx = -1;
			for(int j=i+1;j<2*N;j++){
				if(s[j]==abs(s[i])){
					idx=j;
					break;
				}
			}
			assert(idx!=-1);
			res += idx-(i+1);
			make_swap(i+1,idx);
		}
		else{
			assert(s[i]>0);
			int idx=-1;
			for(int j=i+1;j<2*N;j++){
				if(s[j]==-abs(s[i])){
					idx=j;
					break;
				}
			}
			assert(idx!=-1);
			res += idx-i;
			make_swap(i,idx);
		}
	}

	return res;
}

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