Submission #598027

#	Time	Username	Problem	Language	Result	Execution time	Memory
598027		yutabi	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	80 ms	73128 KiB

shoes

#include "shoes.h"


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



long long count_swaps(std::vector <int> s)
{
	int n=s.size()/2;

	vector <queue <int> > q(n+1);

	int k=1;

	vector <int> nw(2*n);

	for(int i=0;i<s.size();i++)
	{
		if(q[abs(s[i])].size())
		{
			if(q[abs(s[i])].front() < 0 && s[i]>0)
			{
				nw[(-q[abs(s[i])].front())-1]=-k;
				nw[i]=k;

				k++;

				q[abs(s[i])].pop();
			}

			else if(q[abs(s[i])].front() > 0 && s[i]<0)
			{
				nw[(q[abs(s[i])].front())-1]=k;
				nw[i]=-k;

				k++;

				q[abs(s[i])].pop();
			}

			else if(s[i]>0)
			{
				q[abs(s[i])].push(i+1);
			}

			else
			{
				q[abs(s[i])].push(-i-1);
			}
		}

		else if(s[i]>0)
		{
			q[abs(s[i])].push(i+1);
		}

		else
		{
			q[abs(s[i])].push(-i-1);
		}
	}

	vector <int> t(n+1,-1);

	vector <long long> p(2*n);

	k=0;

	for(int i=0;i<nw.size();i++)
	{
		if(t[abs(nw[i])]==-1)
		{
			t[abs(nw[i])]=k;
			k++;
		}

		p[i]=2*t[abs(nw[i])];

		if(nw[i]>0)
		{
			p[i]++;
		}
	}

	/*for(int i=0;i<nw.size();i++)
	{
		printf("%d ",nw[i]);
	}

	printf("\n");

	for(int i=0;i<p.size();i++)
	{
		printf("%lld ",p[i]);
	}

	printf("\n");*/

	long long ans=0;

	k=0;

	long long num=0;

	for(long long i=0;i<p.size();i++)
	{
		while(k<p[i])
		{
			num++;

			k++;
		}

		if(k>p[i])
		{
			num--;
		}

		if(k==p[i])
		{
			k++;
		}

		ans+=num;
	}



	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:19:15: 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:71:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i=0;i<nw.size();i++)
      |              ~^~~~~~~~~~
shoes.cpp:107:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for(long long i=0;i<p.size();i++)
      |                    ~^~~~~~~~~

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