Submission #432695

#	Time	Username	Problem	Language	Result	Execution time	Memory
432695		Kevin_Zhang_TW	Sorting (IOI15_sorting)	C++17	100 / 100	358 ms	23780 KiB

sorting

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 600010;
#include "sorting.h"

int n, a[MAX_N], *s, *p, *q;
int *sx, *sy;

vector<pair<int,int>> count_cost(int *s) {
	vector<int> a(s, s+n);

	vector<pair<int,int>> ret;

	for (int i = 0;i < n;++i) {
		while (a[i] != i) {
			int x = i, y = a[i];
			swap(a[x], a[y]);
			ret.pb(a[x], a[y]);
		}
	} 

	return ret; 
}

int vx[MAX_N], vy[MAX_N], pos[MAX_N];

void mswap_pos(int x, int y) {
	swap(a[x], a[y]);
	swap(pos[ a[x] ], pos[ a[y] ]);
}

bool valid(int len) {
	copy(s, s+n, a);
	for (int i = 0;i < len;++i) {
		swap(a[ sx[i] ], a[ sy[i] ]);
		vx[i] = a[ sx[i] ], vy[i] = a[ sy[i] ];
	}
	auto swv = count_cost(a);
	if (swv.size() > len) return false;

	while (swv.size() < len) swv.pb(0, 0);

	copy(s, s+n, a);
	for (int i = 0;i < n;++i) pos[ a[i] ] = i;
	for (int i = 0;i < len;++i) {
		mswap_pos(sx[i], sy[i]);
		auto [x, y] = swv[i];
		p[i] = pos[x], q[i] = pos[y];
		mswap_pos( pos[x], pos[y] );

	} 

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

	return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	p = P, q = Q, s = S, sx = X, sy = Y;
	n = N;
	for (int i = 0;i < N;++i)
		DE(sx[i], sy[i]);

	int l = 0, r = n, mid;
	while (l < r) {
		mid = l + r >> 1;
		if (valid(mid))
			r =	mid;
		else
			l = mid+1;
	}
	assert(valid(l));
	valid(l);
	DE(l);
	return l; 
}

Compilation message (stderr)

sorting.cpp: In function 'std::vector<std::pair<int, int> > count_cost(int*)':
sorting.cpp:24:39: warning: declaration of 's' shadows a global declaration [-Wshadow]
   24 | vector<pair<int,int>> count_cost(int *s) {
      |                                  ~~~~~^
sorting.cpp:21:19: note: shadowed declaration is here
   21 | int n, a[MAX_N], *s, *p, *q;
      |                   ^
sorting.cpp:25:14: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   25 |  vector<int> a(s, s+n);
      |              ^
sorting.cpp:21:8: note: shadowed declaration is here
   21 | int n, a[MAX_N], *s, *p, *q;
      |        ^
sorting.cpp: In function 'bool valid(int)':
sorting.cpp:54: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]
   54 |  if (swv.size() > len) return false;
      |      ~~~~~~~~~~~^~~~~
sorting.cpp:56:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |  while (swv.size() < len) swv.pb(0, 0);
      |         ~~~~~~~~~~~^~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
sorting.cpp:76:3: note: in expansion of macro 'DE'
   76 |   DE(sx[i], sy[i]);
      |   ^~
sorting.cpp:80:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |   mid = l + r >> 1;
      |         ~~^~~
sorting.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
sorting.cpp:88:2: note: in expansion of macro 'DE'
   88 |  DE(l);
      |  ^~
sorting.cpp:72:39: warning: unused parameter 'M' [-Wunused-parameter]
   72 | 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