Submission #331230

#	Time	Username	Problem	Language	Result	Execution time	Memory
331230		pggp	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	99 ms	69760 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

int sgn(int x){
	if(x > 0 )	return 1;
	return - 1;
}

long long count_swaps(vector < int > S){
	// Najpierw przenumerowanie
	set < int > sizes_set;
	vector < int > sizes_original;
	map < int, int > map_sizes;
	bool b = true;
	for (int i = 0; i < S.size()/2; ++i)
	{
		if(S[i] != -S[i + S.size()/2] or S[i] > 0){
			b = false;
		}
		
	}

	if(b){
		long long n = S.size()/2;
		return n * (n - 1) / 2;
	}

	// Na początku zamiany wewnętrzne
	long long interial = 0;


	stack < int > size_stack[S.size()/2 + 1];
	for (int i = 0; i < S.size(); ++i)
	{
		if(size_stack[abs(S[i])].empty()){
			size_stack[abs(S[i])].push(S[i]);
		}
		else{
			if(S[i] < 0){
				if(size_stack[abs(S[i])].top() > 0){
					interial += size_stack[abs(S[i])].size();
					size_stack[abs(S[i])].pop();
				}
				else{
					size_stack[abs(S[i])].push(S[i]);
				}
			}
			else{
				if(size_stack[S[i]].top() < 0){
					interial += size_stack[S[i]].size() - 1;
					size_stack[S[i]].pop();
				}
				else{
					size_stack[S[i]].push(S[i]);
				}
			}
		
		}
	}

	long long exterial = 0;

	

	return interial + exterial;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:16:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for (int i = 0; i < S.size()/2; ++i)
      |                  ~~^~~~~~~~~~~~
shoes.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  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