Submission #426125

#TimeUsernameProblemLanguageResultExecution timeMemory
426125_fractalSorting (IOI15_sorting)C++14
100 / 100
522 ms28004 KiB
#include "sorting.h" #include <iostream> #include <algorithm> #include <stack> using namespace std; int findSwapPairs(int N, int SS[], int M, int X[], int Y[], int P[], int Q[]) { int A[N], pos[N], sop[N], L[M], R[M], ret = (1<<30), S[N]; int tl = 0, tr = M - 1; while (tl <= tr) { int m = tl + tr >> 1; for (int i = 0; i < N; ++i) A[i] = i, S[i] = SS[i]; for (int i = m; i >= 0; --i) swap(A[X[i]], A[Y[i]]); int bad = 0; for (int i = 0; i < N; ++i) if (S[i] != i) bad++; int r = -1; stack<int>s; for (int j = 0; j < N; ++j) pos[A[j]] = j, sop[S[j]] = j, s.push(j); for (int i = 0; i <= m; ++i) { P[i] = Q[i] = 0; if (bad == 0) { r = i; break; } if (S[X[i]] != X[i]) bad--; if (S[Y[i]] != Y[i]) bad--; swap(S[X[i]], S[Y[i]]); swap(pos[A[X[i]]], pos[A[Y[i]]]); swap(sop[S[X[i]]], sop[S[Y[i]]]); swap(A[X[i]], A[Y[i]]); if (S[X[i]] != X[i]) bad++; if (S[Y[i]] != Y[i]) bad++; if (bad == 0) { r = i + 1; break; } while (s.size() && sop[s.top()] == pos[s.top()]) s.pop(); if (s.size()) { Q[i] = sop[s.top()]; P[i] = pos[s.top()]; s.pop(); } if (S[Q[i]] != Q[i]) bad--; if (S[P[i]] != P[i]) bad--; swap(S[Q[i]], S[P[i]]); swap(sop[S[Q[i]]], sop[S[P[i]]]); if (S[Q[i]] != Q[i]) bad++; if (S[P[i]] != P[i]) bad++; } if (bad) { tl = m + 1; continue; } tr = m - 1; if (r == -1) r = m + 1; if (ret >= r) { ret = r; for (int i = 0; i < r; ++i) L[i] = Q[i], R[i] = P[i]; } } for (int i = 0; i < ret; ++i) Q[i] = L[i], P[i]= R[i]; return ret; }

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:12:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |   int m = tl + tr >> 1;
      |           ~~~^~~~
#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...