Submission #703206

#	Time	Username	Problem	Language	Result	Execution time	Memory
703206		Doncho_Bonboncho	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	30 ms	4932 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

typedef long long ll;

const int MAX_N = 1e6 + 42;

int p[MAX_N];
int last[MAX_N];

ll tree[MAX_N];

void add( int x, int v ){
//	std::cerr<<" ! "<<x<<"\n";
	while( x < MAX_N ){
		tree[x] += v;
		x += x&(-x);
	}
}

int query( int x ){
	int nas = 0;
	while( x ){
		nas += tree[x];
		x -= x&(-x);
	}
	return nas;
}

bool oke[MAX_N];
bool l[MAX_N];

long long count_swaps(std::vector<int> s) {

	ll nas = 0; 
	
	int n = s.size();
	for( int i=1 ; i<=n ; i++ ){
		if( s[i-1] < 0 ) l[i] = true;
		int curr = abs( s[i-1] );
	//	std::cerr<<" ! "<<curr<<"\n";
	//	std::cerr<<last[curr]<<"\n";
		if( last[curr] == 0 ) last[curr] = i;
		else{
			p[i] = last[curr];
			p[last[curr]] = i;

			last[curr] = 0;
 		}
		add( i, 1 );
	}

	/*
	for( int i=1 ; i<=n ; i++ )
		std::cerr<<p[i]<<" ";
	std::cerr<<"\n";
	*/

	for( int i=1 ; i<=n ; i++ ){
		while( i<=n and oke[i] ) i++;
		if( i > n ) break;

		ll currNas = query( p[i] )-1;
		if( l[i] ){
	//		std::cerr<<"l -> -1 \n";
			currNas --;
		}

	//	std::cerr<<" ! "<<i<<" "<<p[i]<<" -> "<<currNas<<"\n\n";
		nas += currNas;

		add( i, -1 );
		add( p[i], -1 );

		oke[i] = true;
		oke[p[i]] = true;
	}

	return nas;
}

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