제출 #579775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
579775		Clan328	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1085 ms	10132 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

long long count_swaps(std::vector<int> s) {
	int n = s.size()/2;

	int res = 0;
	for (int i = 0; i < n; i++) {
		map<int, pair<int, int>> pos;
		for (int j = 2*i; j < 2*n; j++) {
			if (pos.count(abs(s[j])) == 0) {
				if (s[j] < 0) pos[abs(s[j])] = {j, -1};
				else pos[abs(s[j])] = {-1, j};
			} else {
				if (s[j] < 0 && pos[abs(s[j])].first == -1) pos[abs(s[j])].first = j;
				else if (s[j] > 0 && pos[abs(s[j])].second == -1) pos[abs(s[j])].second = j;
			}
		}

		int dist = -1;
		int pos1, pos2;
		for (auto[key, arc] : pos) {
			int left = arc.first, right = arc.second;

			int tmp = 0;
			if (left < right) tmp = left-2*i + right-2*i-1;
			else tmp = left-2*i + right-2*i;

			// cout << tmp << " "<<  left << " " << right << endl;

			if (dist == -1 || tmp < dist) {
				dist = tmp;
				pos1 = left;
				pos2 = right;
			}
		}

		res += dist;
		// cout << res << endl;
		// cout << dist << " "<<  pos1 << " " << pos2 << endl;

		vector<int> tmp(2*n);
		for (int j = 0; j < 2*i; j++) {
			tmp[j] = s[j];
		}
		tmp[2*i] = s[pos1];
		tmp[2*i+1] = s[pos2];

		int idx = 2*i;
		// cout << s[0] << endl;
		for (int j = 2*i+2; j < 2*n; j++) {
			while (idx == pos1 || idx == pos2) {
				idx++;
			}
			tmp[j] = s[idx];
			idx++;
		}

		// cout << tmp[2] << endl;

		s = tmp;

		// t1 = s[pos1];
		// t2 = s[pos2];
		// for (int j = i; j < max(pos1, pos2)+1; j++) {
		// 	if (j % 2 == 0) {
		// 		int tmp = s[j];
		// 		s[j] = t1;
		// 		t1 = tmp;
		// 	} else {
		// 		int tmp = s[j];
		// 		s[j] = t2;
		// 		t2 = tmp;
		// 	}
		// }

		// for (int j = 0; j < 2*n; j++) cout << s[j] << " ";
		// 	cout << endl;
	}

	return res;
}

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:49:22: warning: 'pos2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |   tmp[2*i+1] = s[pos2];
      |                      ^
shoes.cpp:48:20: warning: 'pos1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |   tmp[2*i] = s[pos1];
      |                    ^

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