Submission #1086777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086777		quangminh412	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	17 ms	2764 KiB

shoes

#include <bits/stdc++.h>
using namespace std;

/*
  John Watson
  https://codeforces.com/profile/quangminh98

  Mua Code nhu mua Florentino !!
*/

#define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

ll count_swaps(vector<int> s)
{
	int n = s.size() / 2;
	bool sub3 = true, sub4 = true;
	int check = -1;
	for (int i = 0; i < s.size(); i++)
	{
		if (check == -1) check = abs(s[i]); else if (check != abs(s[i])) sub3 = false;
		if (i < n && s[i] > 0) sub4 = false;
		if (i >= n && s[i] < 0) sub4 = false;
		if (i < n && s[i] + s[i + n] != 0) sub4 = false;
	}
	
	if (n == 1)
	{
		// sub1
		return (s[0] < 0 ? 0 : 1);
	} else
	if (sub3 == true)
	{
		ll res1 = 0, res2 = 0;
		int cur1 = 0, cur2 = 0;
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] < 0) 
			{
				res1 += abs(i - cur1 * 2);
				cur1++;
			} else
			{
				res2 += abs(i - cur2 * 2 - 1);
				cur2++;
			}
		}
		return min(res1, res2);
	} else
	if (sub4 == true)
	{
		ll res = 0;
		for (int i = n - 1; i >= 0; i--)
			res += i;
		return res;
	}
	ll ans = 0;
	
	unordered_map<int, queue<int>> mark;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] < 0) mark[s[i]].push(i); 
		else
		{
			int pos = mark[-s[i]].front(); 
			mark[-s[i]].pop();
			ans += abs(i - pos) - 1;
		}
	}
	return ans;
}

Compilation message (stderr)

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

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