Submission #419039

#	Time	Username	Problem	Language	Result	Execution time	Memory
419039		EncryptingWolf	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	426 ms	35500 KiB

shoes

#include <vector>
#include <iostream>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
#define FOR(i,x,y) for (ll i = x; i <y; i++)

vector<ll> fenwick(1000000);

void update(ll i, ll a)
{
	i++;
	while (i < fenwick.size())
	{
		fenwick[i]+=a;
		i += (i&(-i));
	}
}

ll sum(ll i)
{
	i++;
	ll sum = 0;
	while (i > 0)
	{
		sum+=fenwick[i];
		i -= (i&(-i));
	}
	return sum;
}

ll count_swaps(vector<int> K)
{
	vector<ll> reNum;
	map<ll,ll> count;
	vector<ll> S;
	FOR(i, 0, K.size())
	{
		S.push_back(K[i]);
	}

	FOR(i, 0, S.size())
	{
		reNum.push_back((count[S[i]] * S.size()*(abs(S[i])/S[i]) + S[i]));
		count[S[i]]++;
	}
	vector<ll> reNum2;
	map<ll, ll> numMap2;
	ll available = 1;
	FOR(i, 0, S.size())
	{
		auto a = numMap2[abs(reNum[i])];
		if (a == 0)
		{
			numMap2[abs(reNum[i])] = available*2;
			if (reNum[i]<0)
				reNum2.push_back(available*2-1);
			else
				reNum2.push_back(available*2);
			available++;

		}
		else
		{
			if (reNum[i] < 0)
				reNum2.push_back(a - 1);
			else
				reNum2.push_back(a);
		}
	}
	ll total = 0;
	update(reNum2[S.size()-1], 1);
	for (ll i = S.size() - 2; i >= 0; i--)
	{
		total += sum(reNum2[i]);
		update(reNum2[i], 1);
	}
	return total;
}

Compilation message (stderr)

shoes.cpp: In function 'void update(ll, ll)':
shoes.cpp:14:11: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  while (i < fenwick.size())
      |         ~~^~~~~~~~~~~~~~~~
shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:7:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i,x,y) for (ll i = x; i <y; i++)
......
   38 |  FOR(i, 0, K.size())
      |      ~~~~~~~~~~~~~~                  
shoes.cpp:38:2: note: in expansion of macro 'FOR'
   38 |  FOR(i, 0, K.size())
      |  ^~~
shoes.cpp:7:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i,x,y) for (ll i = x; i <y; i++)
......
   43 |  FOR(i, 0, S.size())
      |      ~~~~~~~~~~~~~~                  
shoes.cpp:43:2: note: in expansion of macro 'FOR'
   43 |  FOR(i, 0, S.size())
      |  ^~~
shoes.cpp:7:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define FOR(i,x,y) for (ll i = x; i <y; i++)
......
   51 |  FOR(i, 0, S.size())
      |      ~~~~~~~~~~~~~~                  
shoes.cpp:51:2: note: in expansion of macro 'FOR'
   51 |  FOR(i, 0, S.size())
      |  ^~~

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