제출 #331223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
331223		pggp	Arranging Shoes (IOI19_shoes)	C++14	30 / 100	108 ms	71020 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])];
	}

	// 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;
}

컴파일 시 표준 에러 (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:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for (int i = 0; i < S.size(); ++i)
      |                  ~~^~~~~~~~~~

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