Submission #64700

#	Time	Username	Problem	Language	Result	Execution time	Memory
64700		FLDutchman	Sorting (IOI15_sorting)	C++14	100 / 100	434 ms	32368 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define int long long
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define pb push_back
#define fst first
#define snd second
#define LSB(k) k&-k

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

const int mod = 1e9+7;

int N, M;
vi S, X, Y, P, Q;
vii swaps;

bool solve(int R){
	swaps.clear();
	vi perm = S;
	FOR(i, 0, R) swap(perm[X[i]], perm[Y[i]]);
	// VALUES that should be swapped
	vi idx(N);
	FOR(i, 0, N) idx[perm[i]] = i;
	int cnt = 0;
	FOR(i, 0, N){
		if(i != perm[i]) {
			cnt++;
			swaps.pb({perm[i], i});
			//cout << perm[i] << " " << i << endl;
			int pi = perm[i]; 
			swap(perm[i], perm[idx[i]]);
			swap(idx[i], idx[pi]);
		}
	}
	FOR(i, swaps.size(), R) swaps.pb({0, 0});
	//for(int i : perm) cout << i << " ";
	//cout << endl;
	return cnt <= R;
}

INT findSwapPairs(INT n, INT s[], INT m, INT x[], INT y[], INT p[], INT q[]) {
	N = n; M = m;
    FOR(i, 0, N) S.pb(s[i]);
	FOR(i, 0, M) X.pb(x[i]), Y.pb(y[i]);

	int lb = -1, rb = M;
	while(lb + 1 != rb){
		int mb = (lb+rb)/2;
		if(solve(mb)) rb = mb;
		else lb = mb;
	}
	solve(rb);

	vi idx(N);
	FOR(i, 0, N) idx[S[i]] = i;
	FOR(i, 0, swaps.size()){
		swap(idx[S[X[i]]], idx[S[Y[i]]]);
		swap(S[X[i]], S[Y[i]]);
		p[i] = idx[swaps[i].fst];
		q[i] = idx[swaps[i].snd];
		swap(S[idx[swaps[i].fst]], S[idx[swaps[i].snd]]);
		swap(idx[swaps[i].fst], idx[swaps[i].snd]);
	}

	return swaps.size();
}

Compilation message (stderr)

sorting.cpp: In function 'INT findSwapPairs(INT, INT*, INT, INT*, INT*, INT*, INT*)':
sorting.cpp:8:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = (l); i < (r); i++)
                                         ^
sorting.cpp:63:2: note: in expansion of macro 'FOR'
  FOR(i, 0, swaps.size()){
  ^~~
sorting.cpp:66:26: warning: conversion to 'INT {aka int}' from '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' may alter its value [-Wconversion]
   p[i] = idx[swaps[i].fst];
                          ^
sorting.cpp:67:26: warning: conversion to 'INT {aka int}' from '__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type {aka long long int}' may alter its value [-Wconversion]
   q[i] = idx[swaps[i].snd];
                          ^
sorting.cpp:72:19: warning: conversion to 'INT {aka int}' from 'std::vector<std::pair<long long int, long long int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  return swaps.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