Submission #824517

#	Time	Username	Problem	Language	Result	Execution time	Memory
824517		caganyanmaz	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	180 ms	32932 KiB

shoes

#include <bits/stdc++.h>
#define mp(x...) array<int, 2>({x})
#define pb push_back
#define int int64_t
#define vi vector<int32_t> 
using namespace std;
#include "shoes.h"

constexpr static int MXSIZE = 1e6;

struct Fenwick
{
	int v[MXSIZE];
	void set(int i, int val) { for (++i;i<MXSIZE;i+=i&(-i)) v[i] += val; }
	int get(int i) { int res = 0; for(++i;i>0;i-=i&(-i)) res += v[i]; return res; }
	int get(int l, int r) { return get(r) - get(l); }
};

int subtask1(vi& s)
{
	if (s[0] > 0)
		return 1;
	else
		return 0;
}

Fenwick fw;
int last[2][MXSIZE];
bitset<MXSIZE> paired;

map<array<int, 2>, int> p;


long long count_swaps(vi s)
{
	for (int i = 0; i < s.size(); i++)
	{
		int j = s[i] > 0 ? 1 : 0;
		array<int, 2> q = {s[i], last[j][abs(s[i])]};
		p[q] = i;
		last[j][abs(s[i])]++;
	}
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < MXSIZE; j++)
			last[i][j] = 0;
	int res = 0;
	for (int i = 0; i < s.size(); i++)
	{
		int j = s[i] > 0 ? 1 : 0;
		array<int, 2> q = {-s[i], last[j][abs(s[i])]};

		last[j][abs(s[i])]++;
		if (paired[i])
			continue;
	
		int ps = p[q];
		paired[ps] = true;
		res += ps - i - 1 - fw.get(i, ps);
		if (s[i] > 0)
			res++;
		fw.set(ps, 1);
	}
	return res;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (int i = 0; i < s.size(); i++)
      |                  ~~^~~~~~~~~~
shoes.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (int i = 0; i < s.size(); i++)
      |                  ~~^~~~~~~~~~

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