Submission #289860

#	Time	Username	Problem	Language	Result	Execution time	Memory
289860		Bill_00	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	206 ms	269688 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
queue<int> l[200005], r[200005];
long long s[200005];
int a[200005];
int n;
long long tree[1000005];
void add(int i, int x)
{
	while(i <= 2 * n)
	{
		s[i] += x;
		i += i & (-i);
	}
}
long long sum(int i)
{
	long long res = 0;
	while(i > 0)
	{
		res += s[i];
		i -= i & (-i);
	}
	return res;
}
long long count_swaps(vector<int> b) {
	int n=b.size();
	n=n/2;
	for(int i=0;i<b.size();i++){
		a[i+1]=b[i];
	}
	int i, j;
	long long ans = 0;
	for(i = 1; i <= 2 * n; i++) 
	{
		if(a[i] > 0) r[a[i]].push(i);
		else l[-a[i]].push(i);
	}
	for(i = 1; i <= 2 * n; i++) add(i, 1);
	for(i = 1; i <= 2 * n; i++) if(sum(i) - sum(i - 1) > 0){
		if(a[i] < 0)
		{
			int id;
			id = r[-a[i]].front();
			ans += sum(id) - sum(i) - 1;
			add(id, -1);
			l[-a[i]].pop();
			r[-a[i]].pop();
		}
		else {
			int id;
			id = l[a[i]].front();
			ans += sum(id) - sum(i);
			add(id, -1);
			l[a[i]].pop();
			r[a[i]].pop();
		}
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:30:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i=0;i<b.size();i++){
      |              ~^~~~~~~~~
shoes.cpp:33:9: warning: unused variable 'j' [-Wunused-variable]
   33 |  int i, j;
      |         ^

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