Submission #1195233

#TimeUsernameProblemLanguageResultExecution timeMemory
1195233madamadam3Sorting (IOI15_sorting)C++20
8 / 100
342 ms589824 KiB
#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; int curturn = 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 = sz(swaps); FOR(i, 0, R) { P[i] = swaps[i].first; Q[i] = swaps[i].second; } 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; } // trace(best.cur); cout << "\n"; R += nR; return R; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...