Submission #676035

#	Time	Username	Problem	Language	Result	Execution time	Memory
676035		atcgu	Sorting (IOI15_sorting)	C++14	100 / 100	276 ms	33840 KiB

sorting

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000010;

typedef pair<int, int> ii;
typedef long long ll;

int n, m;
vector<int> ar;

int ar1[MAXN], ar2[MAXN];

vector<ii> ans;

bool check(int t) {
	vector<int> cur = ar;
	for (int i = 0; i < t; i++) {
		swap(cur[ar1[i]], cur[ar2[i]]);
	}
	vector<ii> swaps;
	for (int i = 0; i < n; i++) {
		while (cur[i] != i) {
			swaps.emplace_back(cur[i], cur[cur[i]]);
			swap(cur[i], cur[cur[i]]);
		}
	}
	while (swaps.size() < t) swaps.emplace_back(0, 0);
	if (swaps.size() > t) return false;
	cur = ar;
	vector<int> ind(n);
	for (int i = 0; i < n; i++) {
		ind[cur[i]] = i;
	}
	vector<ii> ret;
	for (int i = 0; i < t; i++) {
		int x = ar1[i];
		int y = ar2[i];
		swap(ind[cur[x]], ind[cur[y]]);
		swap(cur[x], cur[y]);

		x = swaps[i].first;
		y = swaps[i].second;
		ret.emplace_back(ind[x], ind[y]);
		swap(cur[ind[x]], cur[ind[y]]);
		swap(ind[x], ind[y]);
	}
	ans = ret;
	return true;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	n = N;
	ar = vector<int>(n);
  	for (int i = 0; i < n; i++) ar[i] = S[i];
  	m = M;
  	for (int i = 0; i < m; i++) {
      ar1[i] = X[i];
      ar2[i] = Y[i];
    }
	int lo = 0, hi = m;
	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
		if (check(mid)) {
			hi = mid;
		}
		else lo = mid + 1;
	}
	check(lo);
	for (int i = 0; i < ans.size(); i++) {
      P[i] = ans[i].first;
      Q[i] = ans[i].second;
	}
  	return ans.size();
}

Compilation message (stderr)

sorting.cpp: In function 'bool check(int)':
sorting.cpp:29:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |  while (swaps.size() < t) swaps.emplace_back(0, 0);
      |         ~~~~~~~~~~~~~^~~
sorting.cpp:30:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |  if (swaps.size() > t) return false;
      |      ~~~~~~~~~~~~~^~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i = 0; i < ans.size(); i++) {
      |                  ~~^~~~~~~~~~~~
sorting.cpp:75:19: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   75 |    return ans.size();
      |           ~~~~~~~~^~

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