oj.uz

Submission #124568

# Submission time Handle Problem Language Result Execution time Memory
124568 2019-07-03T13:57:32 Z RockyB Sorting (IOI15_sorting) C++14
100 / 100
 251 ms 27480 KB 
/// In The Name Of God

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

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

const int MAXN = (int)6e5 + 7;

using namespace std;

int n, m;
int a[MAXN], b[MAXN], x[MAXN], y[MAXN];

bool check(int len) {
	rep(i, 0, n) {
		b[i] = a[i];
	}
	rep(i, 0, len) {
		swap(b[x[i]], b[y[i]]);
	}
	int pos[n];
	rep(i, 0, n) {
		pos[b[i]] = i;
	}
	int cnt = 0;
	rep(i, 0, n) {
		if (b[i] != i) {
			swap(b[i], b[pos[i]]);
			swap(pos[b[i]], pos[b[pos[i]]]);
			++cnt;
		}
	}
	if (cnt > len) return 0;
	return 1;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	{
		n = N;
		m = M;
		rep(i, 0, n) {
			a[i] = S[i];
		}
		rep(i, 0, m) {
			x[i] = X[i];
			y[i] = Y[i];
		}
	} 

	// copying
	
	int l = 0, r = m, res = -1;	
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) res = mid, r = mid - 1;
		else l = mid + 1;
	}
	assert(res != -1);
	// opt len found

	rep(i, 0, res) {
		P[i] = Q[i] = 0;
	}
	rep(i, 0, n) {
		b[i] = a[i];
	}
	rep(i, 0, res) {
		swap(b[x[i]], b[y[i]]);
	}
	vector <int> st;
	int go[n], pos[n], fnd[n];
	rep(i, 0, n) {
		go[b[i]] = i;
		pos[i] = b[i];
	}
	rep(i, 0, n) {
		if (go[i] != i) st.pb(i);
	}
	int ptr = 0;
	if (!sz(st)) {
		ptr = 0;
		P[ptr] = 0;
		Q[ptr] = 0;
		return res;
	}
	swap(a[X[ptr]], a[Y[ptr]]);
	rep(i, 0, n) {
		fnd[a[i]] = i;
	}

	for (auto x : st) {
		if (go[x] == x) {
			continue;
		}
		/* rep(i, 0, n) {
			cerr << a[i] << ' ';
		}
		cerr << nl;
		rep(i, 0, n) {
			cerr << go[i] << ' ';
		}
		cerr << nl; */

		int p1 = fnd[x];

		//cerr << a[p1] << ' ' << x << nl;


		rep(i, 0, n) {
			i = pos[x];
			if (go[i] == x) {
				int p2 = fnd[i];
				//cerr << a[p2] << ' ' << i << nl;
				P[ptr] = p1;
				Q[ptr] = p2;
				swap(go[x], go[i]);
				swap(pos[go[x]], pos[go[i]]);
				swap(fnd[x], fnd[i]);
				swap(a[p1], a[p2]);
				ptr++;
				break;
			}
			break;
		}

		/*		
		cerr << " -> " << x << nl;
		rep(i, 0, n) cerr << a[i] << ' ';
		cerr << nl;
		rep(i, 0, n) cerr << go[i] << ' ';
		cerr << nl << nl;*/
		
		if (ptr < m) {
			swap(a[X[ptr]], a[Y[ptr]]);
			swap(fnd[a[X[ptr]]], fnd[a[Y[ptr]]]);
			///// don't use/// swap(go[a[X[ptr]]], go[a[Y[ptr]]]);
		}
	}

	
	return res;
}

#ifdef IOI2018

namespace gen {


	void gen() {
		int N, M;
		N = rand() % 5 + 1;
		int *S = (int*)malloc(sizeof(int) * (unsigned int)N);
		for (int i = 0; i < N; ++i)
			S[i] = i;
		random_shuffle(S, S + N);

		printf ("%d\n", N);
		fflush(stdout);
		int A[N];
		for (int i = 0; i < N; i++) {
				A[i] = S[i];
				printf ("%d ", A[i]);
		}
		printf ("\n");
		fflush(stdout);

		M = rand() % 5 + 1;
		printf ("%d\n", M);
		fflush(stdout);
		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] = rand() % N;
				Y[i] = rand() % N;
				printf ("%d %d\n", X[i], Y[i]);
				fflush(stdout);
		}
		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);
		printf("%d\n", ans);
		fflush(stdout);

		//assert(ans <= 30 * N);
		for (int i = 0; i < ans; ++i) {
					if (i < M) swap(A[X[i]], A[Y[i]]);
					swap(A[P[i]], A[Q[i]]);
			}
			for (int i = 0; i < N; i++) {
				//assert(A[i] == i);
					printf("%d ", A[i]);
			}
			for (int i = 0; i < N; i++) {
					assert(A[i] == i);
					//printf("%d ", A[i]);
			}
	}

}

int main() {
	rep(i, 1, 1000) {
		printf ("Case: %d\n", i);
		fflush(stdout);
		srand(i);
		gen :: gen();
		printf ("\n");
		fflush(stdout);
	}
}

#endif

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:108:12: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  for (auto x : st) {
            ^
sorting.cpp:30:23: note: shadowed declaration is here
 int a[MAXN], b[MAXN], x[MAXN], y[MAXN];
                       ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 372 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 372 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 3 ms 632 KB Output is correct
22 Correct 3 ms 632 KB Output is correct
23 Correct 3 ms 632 KB Output is correct
24 Correct 3 ms 632 KB Output is correct
25 Correct 3 ms 636 KB Output is correct
26 Correct 3 ms 632 KB Output is correct
27 Correct 3 ms 632 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 508 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 2 ms 504 KB Output is correct

Subtask #6
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 508 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 504 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 2 ms 504 KB Output is correct
15 Correct 194 ms 16744 KB Output is correct
16 Correct 204 ms 24868 KB Output is correct
17 Correct 251 ms 26188 KB Output is correct
18 Correct 83 ms 20600 KB Output is correct
19 Correct 178 ms 24720 KB Output is correct
20 Correct 195 ms 25600 KB Output is correct
21 Correct 187 ms 25460 KB Output is correct
22 Correct 194 ms 21748 KB Output is correct
23 Correct 217 ms 27236 KB Output is correct
24 Correct 238 ms 26864 KB Output is correct
25 Correct 229 ms 26488 KB Output is correct
26 Correct 186 ms 25512 KB Output is correct
27 Correct 172 ms 24696 KB Output is correct
28 Correct 233 ms 26612 KB Output is correct
29 Correct 232 ms 25984 KB Output is correct
30 Correct 139 ms 24040 KB Output is correct
31 Correct 231 ms 26648 KB Output is correct
32 Correct 210 ms 26364 KB Output is correct
33 Correct 247 ms 26956 KB Output is correct
34 Correct 216 ms 26612 KB Output is correct
35 Correct 180 ms 24464 KB Output is correct
36 Correct 69 ms 22904 KB Output is correct
37 Correct 241 ms 27480 KB Output is correct
38 Correct 231 ms 26488 KB Output is correct
39 Correct 240 ms 26740 KB Output is correct