Submission #257829

#	Time	Username	Problem	Language	Result	Execution time	Memory
257829		shrek12357	Sorting (IOI15_sorting)	C++14	0 / 100	1 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<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: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