Submission #707037

#	Time	Username	Problem	Language	Result	Execution time	Memory
707037		marvinthang	Sorting (IOI15_sorting)	C++17	100 / 100	197 ms	12476 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    auto check = [&] (int r, bool trace = false) {
    	vector <int> perm(S, S + N);
    	REP(i, r) swap(perm[X[i]], perm[Y[i]]);
    	vector <int> pos(N);
    	REP(i, N) pos[perm[i]] = i;
    	vector <pair <int, int>> swaps;
    	auto __swap = [&] (int i, int j) {
			swap(perm[i], perm[j]);
			swap(pos[perm[i]], pos[perm[j]]);
    	};
    	REP(i, N) {
    		if (perm[i] != i) {
    			swaps.push_back(make_pair(perm[i], i));
    			__swap(i, pos[i]);
    		}
    	}
    	if (!trace) return swaps.size() <= r;
    	while (swaps.size() < r) swaps.push_back(make_pair(0, 0));
    	copy(S, S + N, perm.begin());
    	REP(i, N) pos[perm[i]] = i;
    	REP(i, r) {
    		__swap(X[i], Y[i]);
    		P[i] = pos[swaps[i].fi];
    		Q[i] = pos[swaps[i].se];
    		__swap(P[i], Q[i]);
    	}
    	return true;
    };
    int l = 0, r = N;
    while (l < r) {
    	int m = l + r >> 1;
    	if (check(m)) r = m;
    	else l = m + 1;
    }
    check(l, true);
    return l;
}

Compilation message (stderr)

sorting.cpp: In lambda function:
sorting.cpp:27:38: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |      if (!trace) return swaps.size() <= r;
      |                         ~~~~~~~~~~~~~^~~~
sorting.cpp:28:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |      while (swaps.size() < r) swaps.push_back(make_pair(0, 0));
      |             ~~~~~~~~~~~~~^~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:41:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |      int m = l + r >> 1;
      |              ~~^~~
sorting.cpp:10:39: warning: unused parameter 'M' [-Wunused-parameter]
   10 | int findSwapPairs(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