Submission #257842

#	Time	Username	Problem	Language	Result	Execution time	Memory
257842		shrek12357	정렬하기 (IOI15_sorting)	C++14	0 / 100	1089 ms	512 KiB

sorting

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include "sorting.h"
using namespace std;

vector<pair<int, int>> toChange;
vector<int> xAns, yAns;

bool check(int mid, int nums[], int n, int x[], int y[]) {
	for (int i = 0; i < mid; i++) {
		int a = nums[x[i]];
		nums[x[i]] = nums[y[i]];
		nums[y[i]] = a;
	}
	int adjList[n + 5]; // can optimize later
	for (int i = 0; i < n; i++) {
		adjList[i] = nums[i];
	}
	int counter = 0;
	bool vis[n + 5];
	for (int i = 0; i < n; i++) {
		vis[i] = false;
	}

	for (int i = 0; i < n; i++) {
		if (vis[i]) {
			continue;
		}
		//DFS because I'm too lazy to make a function
		vector<int> arr;
		vis[i] = true;
		int cur = adjList[i];
		while (cur != i) {
			arr.push_back(cur);
			vis[cur] = true;
			cur = adjList[cur];
		}
		arr.push_back(cur);
		//process the stuff in backwards order so change is correct
		for (int j = arr.size() - 1; j > 0; j--) {
			toChange.push_back(make_pair(arr[0], arr[j]));
		}
		counter++;
	}

	return (n - counter <= mid);
}

void getAns(int mid, int nums[], int n, int x[], int y[]) {
	map<int, int> pos;
	for (int i = 0; i < n; i++) {
		pos[nums[i]] = i;
	}
	for (int i = 0; i < toChange.size(); i++) {
		int a = x[i], b = y[i];
		swap(nums[a], nums[b]);
		pos[nums[a]] = a;
		pos[nums[b]] = b;

		int c = toChange[i].first, d = toChange[i].second;
		nums[pos[c]] = d;
		nums[pos[d]] = c;
		xAns.push_back(pos[c]);
		yAns.push_back(pos[d]);
		int tmp = pos[d];
		pos[d] = pos[c];
		pos[c] = tmp;
	}
	for (int i = 0; i < mid - toChange.size(); i++) {
		xAns.push_back(0);
		yAns.push_back(0);
	}
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	int lo = -1;
	int hi = M;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		if (check(mid,S,N,X,Y)) {
			hi = mid;
		}
		else {
			lo = mid + 1;
		}
		toChange.clear();
	}
	check(lo, S, N, X, Y);
	getAns(lo, S, N, X, Y);
	for (int i = 0; i < xAns.size(); i++) {
		P[i] = xAns[i];
		Q[i] = yAns[i];
	}
	return lo;
}

Compilation message (stderr)

sorting.cpp: In function 'bool check(int, int*, int, int*, int*)':
sorting.cpp:48:27: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   for (int j = arr.size() - 1; j > 0; j--) {
                ~~~~~~~~~~~^~~
sorting.cpp: In function 'void getAns(int, int*, int, int*, int*)':
sorting.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < toChange.size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~
sorting.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < mid - toChange.size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:98:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < xAns.size(); i++) {
                  ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26