Submission #422605

#	Time	Username	Problem	Language	Result	Execution time	Memory
422605		MeGustaElArroz23	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1088 ms	4080 KiB

shoes

#include "shoes.h"
#include <cstdio>
#include <cassert>

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<bool,bool> pbb;
typedef vector<pbb> vbb;
typedef pair<int,int> pii;
typedef vector<pii> vii;

const ll INF=1000000001;


long long count_swaps(std::vector<int> v) {
	int n=v.size()/2;
	ll sol=0;
	for (int i=0;i<n;i++){
		vbb porver(n+1,pbb{true,true});
		vii dondevisto(n+1);
		for (int j=2*i;j<2*n;j++){
			int x=v[j];
			if (x<0){
				x=-x;
				if (porver[x].first){
					porver[x].first=false;
					dondevisto[x].first=j;
				}
			}
			else{
				if (porver[x].second){
					porver[x].second=false;
					dondevisto[x].second=j;
				}
			}
			if (porver[x]==pbb{false,false}){
				for (int h=dondevisto[x].first;h>2*i;h--){
					sol++;
					swap(v[h],v[h-1]);
				}
				if (dondevisto[x].second<dondevisto[x].first) dondevisto[x].second++;
				for (int h=dondevisto[x].second;h>2*i+1;h--){
					sol++;
					swap(v[h],v[h-1]);
				}
				break;
			}
		}
	}
	return sol;
}

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