oj.uz

Submission #432694

# Submission time Handle Problem Language Result Execution time Memory
432694 2021-06-18T12:26:44 Z Kevin_Zhang_TW Sorting (IOI15_sorting) C++17
0 / 100
 2 ms 460 KB 
#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], pv[MAX_N], qv[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];
		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

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:74:3: note: in expansion of macro 'DE'
   74 |   DE(sx[i], sy[i]);
      |   ^~
sorting.cpp:78:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |   mid = l + r >> 1;
      |         ~~^~~
sorting.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
sorting.cpp:86:2: note: in expansion of macro 'DE'
   86 |  DE(l);
      |  ^~
sorting.cpp:70:39: warning: unused parameter 'M' [-Wunused-parameter]
   70 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
      |                                   ~~~~^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -