Submission #598031

#	Time	Username	Problem	Language	Result	Execution time	Memory
598031		yutabi	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	124 ms	76720 KiB

shoes

#include "shoes.h"


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



int seg_tree[850000];


int n;
int N;


void update(int h, int l=0, int r=N-1, int node=1)
{
	seg_tree[node]++;

	if(l==r)
	{
		return;
	}

	int m=(l+r)/2;

	if(h<=m)
	{
		update(h,l,m,node*2);
	}

	else
	{
		update(h,m+1,r,node*2+1);
	}
}


long long query(int hl, int hr, int l=0, int r=N-1, int node=1)
{
	if(hl<=l && r<=hr)
	{
		return seg_tree[node];
	}

	int m=(l+r)/2;

	int res=0;

	if(hl<=m)
	{
		res+=query(hl,hr,l,m,node*2);
	}

	if(m+1<=hr)
	{
		res+=query(hl,hr,m+1,r,node*2+1);
	}

	return res;
}



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

	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");*/

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

	for(int i=0;i<p.size();i++)
	{
		p_inv[p[i]]=i;
	}

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

	printf("\n");*/


	long long ans=0;

	for(long long i=0;i<p_inv.size();i++)
	{
		ans+=p_inv[i];

		ans-=query(0,p_inv[i]);

		update(p_inv[i]);
	}



	return ans;
}

Compilation message (stderr)

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