Submission #331221

#	Time	Username	Problem	Language	Result	Execution time	Memory
331221		pggp	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1 ms	364 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(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])];
	}

	// 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[S[i]].empty()){
			size_stack[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(abs(S[i]));
				}
			}
			else{
				if(size_stack[S[i]].top() < 0){
					interial += size_stack[S[i]].size();
					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:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  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