Submission #567807

#	Time	Username	Problem	Language	Result	Execution time	Memory
567807		ngpin04	Sorting (IOI15_sorting)	C++17	100 / 100	345 ms	28800 KiB

sorting

#include <bits/stdc++.h>
#include "sorting.h"
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
	return l + rd() % (r - l + 1);
}
const int N = 6e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

int cur[N];
int a[N];
int s[N];
int x[N];
int y[N];
int p[N];
int q[N];
int n,m;

bool vis[N];

bool check(int r) {
	for (int i = 0; i < n; i++)
		a[i] = s[i];

	for (int i = 0; i <= r; i++) 
		swap(a[x[i]], a[y[i]]);
	
	// cerr << r << "\n";
	for (int i = 0; i < n; i++) {
		vis[i] = false;
		// cerr << a[i] << " \n"[i == n - 1];
	}

	vector <pair <int, int>> sw;
	for (int i = 0; i < n; i++) if (!vis[i]) {
		int j = i;
		vector <int> s(1, j);
		vis[j] = true;
		while (!vis[a[j]]) {
			j = a[j];
			vis[j] = true;
			s.push_back(j);
		}

		for (int j = 1; j < (int) s.size(); j++)
			sw.push_back({a[s[j - 1]], a[s[j]]});
	}

	if (sw.size() > r + 1)
		return false;

	for (int i = 0; i < n; i++)
		cur[a[i]] = i;	

	for (int i = r; i >= 0; i--) {
		if (sw.size() == 0) {
			p[i] = q[i] = 0;
			continue;
		}
		auto [u, v] = sw.back();
		sw.pop_back();
		p[i] = cur[u];
		q[i] = cur[v];

		swap(a[cur[u]], a[cur[v]]);
		swap(cur[u], cur[v]);

		swap(cur[a[x[i]]], cur[a[y[i]]]);
		swap(a[x[i]], a[y[i]]);
	}	
	return true;
}

int solve() {
	int lo = -2;
	int hi = m;
	while (hi - lo > 1) {
		int mid = (lo + hi) >> 1;
		if (check(mid))
			hi = mid;
		else
			lo = mid;
	}

	check(hi);
	return hi + 1;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n = N;
    m = M;
    for (int i = 0; i < n; i++)
    	s[i] = S[i];

    for (int i = 0; i < m; i++)
    	x[i] = X[i], y[i] = Y[i];

    int res = solve();
    for (int i = 0; i < res; i++) 
    	P[i] = p[i], Q[i] = q[i];

    for (int i = 0; i < res; i++) {
    	swap(s[x[i]], s[y[i]]);
    	swap(s[p[i]], s[q[i]]);
    }

    // for (int i = 0; i < n; i++)
    // 	cerr << s[i] << " \n"[i == n - 1];
	return res;
}

//#include "grader.cpp"

Compilation message (stderr)

sorting.cpp: In function 'int rand(int, int)':
sorting.cpp:20:11: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 64, 312, 156, 31, 13043109905998158313, 29, 6148914691236517205, 17, 8202884508482404352, 37, 18444473444759240704, 43, 6364136223846793005>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   20 |  return l + rd() % (r - l + 1);
      |         ~~^~~~~~~~~~~~~~~~~~~~
sorting.cpp: In function 'bool check(int)':
sorting.cpp:55:16: warning: declaration of 's' shadows a global declaration [-Wshadow]
   55 |   vector <int> s(1, j);
      |                ^
sorting.cpp:30:5: note: shadowed declaration is here
   30 | int s[N];
      |     ^
sorting.cpp:63:12: warning: declaration of 'j' shadows a previous local [-Wshadow]
   63 |   for (int j = 1; j < (int) s.size(); j++)
      |            ^
sorting.cpp:54:7: note: shadowed declaration is here
   54 |   int j = i;
      |       ^
sorting.cpp:67:16: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |  if (sw.size() > r + 1)
      |      ~~~~~~~~~~^~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:107:23: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  107 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                   ~~~~^
sorting.cpp:22:11: note: shadowed declaration is here
   22 | const int N = 6e5 + 5;
      |           ^

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