Submission #1195273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195273		madamadam3	Sorting (IOI15_sorting)	C++20	0 / 100	1093 ms	676 KiB

sorting

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

using namespace std;

#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define each(a, x) for (auto &x : a) 
#define srt(x) sort(all(x))
#define sz(x) (int) (x).size()
#define pb push_back
#define trace(x) for (auto &el : x) cout << el << " "

using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pi>;

struct State {
	vi cur; int turn;
	vpi steps;
};

bool is_sorted(vi inp) {
	int n = sz(inp);
	vi to_srt = vi(all(inp));
	srt(to_srt);

	FOR(i, 0, n) {
		if (inp[i] != to_srt[i]) return false;
	}
	return true;
}

/*
	N = length of seq
	S = initial seq
	M = swaps by ermek
	X[i], Y[i] = ith swap of ermek
	P[i], Q[i] = swaps player makes
	function returns R (number of swaps)
*/

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	int n = N;
	int R = 1;

	vi initial; FOR(i, 0, n) initial.pb(S[i]);
	vpi swaps;

	if (is_sorted(initial)) return 0;
	swap(initial[X[0]], initial[Y[0]]);
	int curturn = 1;

	while (!is_sorted(initial)) {
		int ni = X[curturn], nj = Y[curturn];
		int ini = initial[ni], inj = initial[nj];
		// cases:
		// initial[nj] = ni and initial[ni] = nj (do our own thing)
		// initial[nj] = ni and initial[ni] != nj or vv (swap the correct thing into place so the swap happens)
		// neither initial[nj] = ni nor initial[ni] = nj (swap any of them? maybe do our own thing? idk if it matters)
		// array is sorted: swap 0 0 
		if (ini == nj && inj == ni) {
			// we can do our own swap here
			FOR(i, 0, n) {
				if (i == ini || i == inj) continue;
				int qidx = 0; while (initial[qidx] != i) qidx++;
				if (qidx == ni || qidx == nj) continue;
				swaps.pb({i, qidx});
				swap(initial[i], initial[qidx]);
				break;
			}
		} else if (ini == nj) {
			int idx = 0; while (initial[idx] != ni) idx++;
			swaps.pb({idx, nj});
			swap(initial[idx], initial[nj]);

		} else if (inj == ni) {
			int idx = 0; while (initial[idx] != nj) idx++;
			swaps.pb({idx, ni});
			swap(initial[idx], initial[ni]);

		} else {
			// int idx = 0; while (initial[idx] != ni) idx++;
			// swaps.pb({idx, nj});
			// swap(initial[idx], initial[nj]);

			FOR(i, 0, n) {
				// if (i == ini || i == inj) continue;
				int qidx = 0; while (initial[qidx] != i) qidx++;
				// if (qidx == ni || qidx == nj) continue;
				swaps.pb({i, qidx});
				swap(initial[i], initial[qidx]);
				break;
			}
		}

		if (is_sorted(initial)) break;

		swap(initial[ni], initial[nj]);
		curturn++;
	}
	swaps.pb({0, 0});

	// FOR(i, 0, n) {
	// 	int qidx = 0;
	// 	while (initial[qidx] != i) qidx++;
	// 	if (qidx == i || qidx <= 1 || i <= 1) continue;
		
	// 	swap(initial[X[curturn]], initial[Y[curturn]]);
	// 	curturn++;
	// 	swap(initial[qidx], initial[i]);
	// 	swaps.pb({i, qidx});
	// }

	R = curturn;
	FOR(i, 0, R) {
		P[i] = swaps[i].first;
		Q[i] = swaps[i].second;
	}

	// trace(initial); cout << "\n";


	// queue<State> q;
	// q.push(State{initial, curturn, {}});

	// State best;
	// while (!q.empty()) {
	// 	auto cur = q.front();
	// 	q.pop();
	// 	if (is_sorted(cur.cur)) {
	// 		best = cur;
	// 		break;
	// 	}

	// 	vi narr = vi(all(cur.cur));
	// 	swap(narr[X[cur.turn]], narr[Y[cur.turn]]);
		
	// 	FOR(i, 0, n) {
	// 		// if (cur.cur[i] == i) continue;
	// 		FOR(j, i + 1, n) {
	// 			// if (cur.cur[j] == j) continue;
	// 			vi nnarr = vi(all(narr));
	// 			swap(nnarr[i], nnarr[j]);
	// 			vpi nsteps = vpi(all(cur.steps));
	// 			nsteps.pb({i, j});

	// 			q.push(State {nnarr, cur.turn + 1, nsteps});
	// 		}
	// 	}
	// }

	// int nR = sz(best.steps);
	// FOR(i, 0, nR) {
	// 	P[i+R] = best.steps[i].first;
	// 	Q[i+R] = best.steps[i].second;
	// }
	// R += nR;

	return R;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26