Submission #331227

#	Time	Username	Problem	Language	Result	Execution time	Memory
331227		pggp	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	230 ms	69612 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;
	for (int i : S)
	{
		if(sizes_set.find(abs(i)) == sizes_set.end()){
			sizes_original.push_back(abs(i));
		}
		sizes_set.insert(abs(i));
	}

	sort(sizes_original.begin(), sizes_original.end());

	for (int i = 0; i < sizes_original.size(); ++i)
	{
		map_sizes[sizes_original[i]] = i + 1;
	}

	for (int i = 0; i < S.size(); ++i)
	{
		S[i] = sgn(S[i]) * map_sizes[abs(S[i])];
	}

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