Submission #422697

#	Time	Username	Problem	Language	Result	Execution time	Memory
422697		MeGustaElArroz23	Arranging Shoes (IOI19_shoes)	C++14	85 / 100	1081 ms	3508 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(x)!=abs(v[0])) return false;
	}
	return true;
}

bool caso_raro(vi v){
	ll n=v.size()/2;
	for(int i=0;i<n;i++){
		if (v[i]>0 or v[n+i]<0 or v[i]!=-v[n+i]) return false;
	}
	return true;
}

ll solve1(vi v){
	//cerr<<1<<'\n';
	int n=v.size()/2;
	ll sol=0;
	ll balance=0;
	for (int x:v){
		if (x<0){
			if (balance>0){
				sol+=balance;
			}
			balance--;
		}
		else{
			if (balance<-1) sol+=-balance-1;
			balance++;
		}
	}
	return sol;
}

ll solve2(vi 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;
}

ll solve3(vi v){
	ll n=v.size()/2;
	return n*(n-1)/2;
}

long long debug(std::vector<int> v) {
	cerr << "begin\n";
	int t=v[0];
	int n=v[1];
	while (t--){
		vi v(2*n,1);
		int counter=n;
		while (counter){
			int x=rand()%(2*n);
			if (v[x]==1){
				v[x]=-1;
				counter--;
			}
		}
		if (solve1(v)!=solve2(v)){
			for (int x:v) cerr << x << ' ';
			cerr<<'\n';
			cerr<< solve1(v) << ' '<<solve2(v)<<'\n';
		}
	}
	cerr << "end\n";
	return 1;
}

long long count_swaps(vi v){
	if (samesize(v)) return solve1(v);
	else if (caso_raro(v)) return solve3(v);
	else return solve2(v);
}

Compilation message (stderr)

shoes.cpp: In function 'll solve1(vi)':
shoes.cpp:35:6: warning: unused variable 'n' [-Wunused-variable]
   35 |  int n=v.size()/2;
      |      ^

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