Submission #707035

#	Time	Username	Problem	Language	Result	Execution time	Memory
707035		marvinthang	Sorting (IOI15_sorting)	C++17	100 / 100	204 ms	21268 KiB

sorting

/*************************************
*    author: marvinthang             *
*    created: 08.03.2023 16:53:13    *
*************************************/

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

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> scan_op(pair <U, V>)  { return in >> u.fi >> u.se; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }

// end of template

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;
}

#ifdef LOCAL 
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;

static inline int _read() {
    if (_charsNumber < 0) {
        exit(1);
    }
    if (!_charsNumber || _currentChar == _charsNumber) {
        _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
        _currentChar = 0;
    }
    if (_charsNumber <= 0) {
        return -1;
    }
    return _buffer[_currentChar++];
}

static inline int _readInt() {
    int c, x, s;
    c = _read();
    while (c <= 32) c = _read();
    x = 0;
    s = 1;
    if (c == '-') {
        s = -1;
        c = _read();
    }
    while (c > 32) {
        x *= 10;
        x += c - '0';
        c = _read();
    }
    if (s < 0) x = -x;
    return x;
}

int main()
{
	_inputFile = fopen("sorting.in", "rb");
	_outputFile = fopen("sorting.out", "w");
	int N, M;
	N = _readInt();
	int *S = (int*)malloc(sizeof(int) * (unsigned int)N);
	int *perm = (int*)malloc(sizeof(int) * (unsigned int)N);
	for (int i = 0; i < N; ++i)
		perm[i] = S[i] = _readInt();
	M = _readInt();
	int *X = (int*)malloc(sizeof(int) * (unsigned int)M), *Y = (int*)malloc(sizeof(int) * (unsigned int)M);
	for (int i = 0; i < M; ++i) {
	    X[i] = _readInt();
	    Y[i] = _readInt();
	}
	int *P = (int*)malloc(sizeof(int) * (unsigned int)M), *Q = (int*)malloc(sizeof(int) * (unsigned int)M);
	int ans = findSwapPairs(N, S, M, X, Y, P, Q);
	fprintf(_outputFile, "%d\n", ans);
	for (int i = 0; i < ans; ++i) {
		swap(perm[X[i]], perm[Y[i]]);
		swap(perm[P[i]], perm[Q[i]]);
		fprintf(_outputFile, "%d %d\n", P[i], Q[i]);
	}
	REP(i, N) fprintf(_outputFile, "%d ", perm[i]);
	return 0;
}
#endif

Compilation message (stderr)

sorting.cpp: In lambda function:
sorting.cpp:63: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]
   63 |      if (!trace) return swaps.size() <= r;
      |                         ~~~~~~~~~~~~~^~~~
sorting.cpp:64: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]
   64 |      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:77:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |      int m = l + r >> 1;
      |              ~~^~~
sorting.cpp:46:39: warning: unused parameter 'M' [-Wunused-parameter]
   46 | 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