Submission #311811

#TimeUsernameProblemLanguageResultExecution timeMemory
311811hhh07Sorting (IOI15_sorting)C++14
100 / 100
465 ms24312 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include "sorting.h" using namespace std; int moze(int n, int s[], int m, int x[], int y[], int p[], int q[]){ int pos[n], s_copy[n], s_copy2[n]; for (int i = 0; i < n; i++) pos[s[i]] = i, s_copy[i] = s[i], s_copy2[i] = s[i]; for (int i = 0; i < m; i++) swap(s[x[i]], s[y[i]]); int kraj_pos[n]; for (int i = 0; i < n; i++) kraj_pos[s[i]] = i; int f[n], g[n]; for (int i = 0; i < n; i++){ f[i] = kraj_pos[s_copy[i]]; g[kraj_pos[s_copy[i]]] = i; } int cnt = 0; for (int i = 0; i < m; i++){ swap(f[x[i]], f[y[i]]); g[f[x[i]]] = x[i]; g[f[y[i]]] = y[i]; swap(s_copy2[x[i]], s_copy2[y[i]]); pos[s_copy2[x[i]]] = x[i]; pos[s_copy2[y[i]]] = y[i]; bool t = false; while(cnt < n){ int idx = g[cnt]; if (s_copy2[idx] != cnt){ int a = idx, b = pos[cnt]; swap(s_copy2[a], s_copy2[b]); p[i] = a; q[i] = b; pos[s_copy2[a]] = a; pos[s_copy2[b]] = b; t = true; break; } cnt++; } if (!t) p[i] = q[i] = 0; else cnt++; } for (int i = 0; i < n; i++) s[i] = s_copy[i]; for (int i = 0; i < n; i++){ if (s_copy2[i] != i) return false; } return true; } int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) { int beg = 0, end = m; while(beg < end){ int mid = (beg + end)/2; for (int i = 0; i < n; i++) p[i] = 0, q[i] = 0; if (moze(n, s, mid, x, y, p, q)) end = mid; else beg = mid + 1; } if (moze(n, s, beg, x, y, p, q)) return beg; }

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
   83 | }
      | ^
#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...