Submission #257828

#	Time	Username	Problem	Language	Result	Execution time	Memory
257828		shrek12357	Sorting (IOI15_sorting)	C++14	0 / 100	1 ms	612 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<int> x, y;
vector<pair<int, int>> toChange;
vector<int> xAns, yAns;

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

	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) {
	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 = 0;
	int hi = m;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		if (check(mid, s, n)) {
			hi = mid;
		}
		else {
			lo = mid + 1;
		}
		toChange.clear();
	}
	check(lo, s, n);
	getAns(lo, s, n);
	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)':
sorting.cpp:46: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)':
sorting.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < toChange.size(); i++) {
                  ~~^~~~~~~~~~~~~~~~~
sorting.cpp:75: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:81:76: warning: declaration of 'y' shadows a global declaration [-Wshadow]
 int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
                                                                            ^
sorting.cpp:14:16: note: shadowed declaration is here
 vector<int> x, y;
                ^
sorting.cpp:81:76: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
                                                                            ^
sorting.cpp:14:13: note: shadowed declaration is here
 vector<int> x, y;
             ^
sorting.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < xAns.size(); i++) {
                  ~~^~~~~~~~~~~~~
sorting.cpp:81:48: warning: unused parameter 'x' [-Wunused-parameter]
 int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
                                                ^
sorting.cpp:81:57: warning: unused parameter 'y' [-Wunused-parameter]
 int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
                                                         ^

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