Submission #785230

#	Time	Username	Problem	Language	Result	Execution time	Memory
785230		ymm	Sorting (IOI15_sorting)	C++17	100 / 100	275 ms	22828 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef std::pair<int,int> pii;
typedef long long ll;
using namespace std;

const int maxn = 200010;
int pos[maxn];
int pospos[maxn];
int pos2[maxn];

void swap_by_idx(int a[], int p[], int i, int j)
{
	swap(p[a[i]], p[a[j]]);
	swap(a[i], a[j]);
}
void swap_by_val(int a[], int p[], int i, int j)
{
	swap_by_idx(a, p, p[i], p[j]);
}

bool can(int r, int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
	Loop (i,0,N)
		pospos[i] = pos[i] = i;
	LoopR (i,0,r)
		swap_by_val(pos, pospos, X[i], Y[i]);
	Loop (i,0,N)
		pos2[S[i]] = i;
	vector<pii> vec;
	vector<int> where_should_go(N);
	Loop (i,0,N)
		where_should_go[pos[i]] = i;
	Loop (i,0,N) {
		while (where_should_go[pos2[i]] != i) {
			vec.push_back({pos2[i], pos2[where_should_go[pos2[i]]]});
			swap(pos2[i], pos2[where_should_go[pos2[i]]]);
		}
	}
	if (vec.size() > r)
		return 0;
	if (P && Q) {
		Loop (i,0,N)
			pos[i] = pospos[i] = i;
		Loop (i,0,vec.size()) {
			swap_by_val(pos, pospos, X[i], Y[i]);
			P[i] = pos[vec[i].first];
			Q[i] = pos[vec[i].second];
		}
		Loop (i,vec.size(),r)
			P[i] = Q[i] = 0;
	}
	return 1;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	int l = 0, r = M;
	while (l < r) {
		int m = (l+r)/2;
		if (can(m, N, S, M, X, Y, 0, 0))
			r = m;
		else
			l = m+1;
	}
	can(l, N, S, M, X, Y, P, Q);
	return l;
}

Compilation message (stderr)

sorting.cpp: In function 'bool can(int, int, int*, int, int*, int*, int*, int*)':
sorting.cpp:27:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   27 |   pospos[i] = pos[i] = i;
      |                        ^
sorting.cpp:31:16: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   31 |   pos2[S[i]] = i;
      |                ^
sorting.cpp:35:29: warning: conversion from 'll' {aka 'long long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   35 |   where_should_go[pos[i]] = i;
      |                             ^
sorting.cpp:42:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |  if (vec.size() > r)
      |      ~~~~~~~~~~~^~~
sorting.cpp:46:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   46 |    pos[i] = pospos[i] = i;
      |                         ^
sorting.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
sorting.cpp:47:3: note: in expansion of macro 'Loop'
   47 |   Loop (i,0,vec.size()) {
      |   ^~~~
sorting.cpp:24:37: warning: unused parameter 'M' [-Wunused-parameter]
   24 | bool can(int r, int N, int S[], int M, int X[], int Y[], int P[], int Q[])
      |                                 ~~~~^

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