제출 #422652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422652		MeGustaElArroz23	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	25 ms	5060 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;

bool samesize(vi v){
	for (int x:v){
		if (abs(v[x])!=abs(v[0])) return false;
	}
	return true;
}

long long count_swaps(std::vector<int> v) {
	int n=v.size()/2;
	ll sol=0;
	if (samesize(v)){
		ll l=0;
		ll r=0;
		for (int x:v){
			if (x<0){
				sol+=abs(2-l-max(l-r,ll(0))-l-r+max(r-l,ll(0)));
				l++;
			}
			else{
				sol+=abs(2*r+1-max(r-l+1,ll(0))-l-r+max(l-r-1,ll(0)));
				r++;
			}
		}
		return sol;
	}
	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: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15