Submission #211109

#	Time	Username	Problem	Language	Result	Execution time	Memory
211109		_Ice_Tea_	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	111 ms	19832 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define LLI long long int
#define pii pair<int,int>
#define ULTRA 2134567890
#define de(x) if( x && x == MODE)
#define MODE 0
using namespace std;

int cht[200007][2];
vector<int> keep[200007][2];

int n;
int bit[200007] = {};
bool v[200007] = {};

void add( int x, int d)
{
	x++;
	while( x <= n)
	{
		bit[x] += d;
		x += x & (-x);
	}
}

LLI query( int x)
{
	LLI sum = 0;
	x++;
	while( x)
	{
		sum += bit[x];
		x -= x & (-x);
	}
	return sum;
}

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

	int i,j;

	n = s.size();
	for( i=n-1; i>0; i--)
	{
		if( s[i] < 0)
			keep[ -s[i] ][0].push_back(i);
		else
			keep[ s[i] ][1].push_back(i);
	}

	for( i=1; i<n; i++)
		add( i, 1);

	LLI ans = 0;
	for( i=0; i<n; i++)
	{
		if( v[i])
			continue;
		de(1)
		{
			printf(" i = %d\n", i);
		}
		v[i] = 1;

		int color = abs( s[i]);
		int match;
		if( s[i] < 0)
		{
			while( v[ keep[color][1].back() ])
				keep[color][1].pop_back();
			match = keep[color][1].back();
			de(1)
			{
				printf("match = %d\n", match);
			}
			ans += query( match) - 1;
			v[ match ] = 1;
		}
		else
		{
			while( v[ keep[color][0].back() ])
				keep[color][0].pop_back();
			match = keep[color][0].back();
			de(1)
			{
				printf("match = %d\n", match);
			}
			ans += query( match);
			v[ match ] = 1;
		}
		add( i, -1);
		add( match, -1);
		de(1) printf("ans = %d\n", ans);
	}

	return ans;
}
/*
int main()
{
	int i,j;
	int n;

	scanf("%d", &n);

	vector<int> s;
	for( i=0; i<n; i++)
	{
		int a;
		scanf("%d", &a);
		s.push_back(a);
	}
	LLI ans = count_swaps(s);
	printf("%lld\n", ans);
	return 0;
}
*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:94:33: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   de(1) printf("ans = %d\n", ans);
                                 ^
shoes.cpp:41:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^

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