| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 55440 |
2018-07-07T11:28:03 Z |
aome |
Sorting (IOI15_sorting) |
C++17 |
|
338 ms |
21064 KB |
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n;
int S[N], X[N * 3], Y[N * 3];
int A[N], B[N], C[N], D[N];
vector< pair<int, int> > vec;
bool check(int len) {
vec.clear();
for (int i = 0; i < n; ++i) A[i] = S[i];
for (int i = 0; i < n; ++i) B[i] = i;
for (int i = 0; i < n; ++i) C[B[i]] = i;
for (int i = 0; i < len; ++i) {
int x = C[X[i]], y = C[Y[i]];
swap(C[X[i]], C[Y[i]]);
swap(B[x], B[y]);
}
for (int i = 0; i < n; ++i) D[A[i]] = i;
for (int i = 0; i < n; ++i) {
if (D[i] == C[i]) continue;
int x = D[i], y = C[i];
vec.push_back({x, y});
swap(D[i], D[A[y]]);
swap(A[x], A[y]);
}
while (vec.size() < len) vec.push_back({0, 0});
return vec.size() == len;
}
int findSwapPairs(int _n, int _S[], int m, int _X[], int _Y[], int P[], int Q[]) {
n = _n;
for (int i = 0; i < n; ++i) {
S[i] = _S[i];
}
for (int i = 0; i < m; ++i) {
X[i] = _X[i];
Y[i] = _Y[i];
}
int l = 0, r = m - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid; else l = mid + 1;
}
int len = l;
check(len);
for (int i = 0; i < n; ++i) B[i] = i;
for (int i = 0; i < n; ++i) C[B[i]] = i;
for (int i = 0; i < len; ++i) {
int x = C[X[i]], y = C[Y[i]];
swap(C[Y[i]], C[X[i]]);
swap(B[x], B[y]);
x = vec[i].first, y = vec[i].second;
P[i] = B[x], Q[i] = B[y];
}
return len;
}
Compilation message
sorting.cpp: In function 'bool check(int)':
sorting.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (vec.size() < len) vec.push_back({0, 0});
~~~~~~~~~~~^~~~~
sorting.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
return vec.size() == len;
~~~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
3 ms |
384 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
3 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
3 ms |
384 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
3 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
3 ms |
384 KB |
Output is correct |
| 10 |
Correct |
3 ms |
384 KB |
Output is correct |
| 11 |
Correct |
3 ms |
512 KB |
Output is correct |
| 12 |
Correct |
3 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
512 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
3 ms |
384 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
3 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
3 ms |
384 KB |
Output is correct |
| 10 |
Correct |
3 ms |
384 KB |
Output is correct |
| 11 |
Correct |
3 ms |
512 KB |
Output is correct |
| 12 |
Correct |
3 ms |
384 KB |
Output is correct |
| 13 |
Correct |
3 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 ms |
384 KB |
Output is correct |
| 15 |
Correct |
3 ms |
512 KB |
Output is correct |
| 16 |
Correct |
4 ms |
384 KB |
Output is correct |
| 17 |
Correct |
4 ms |
384 KB |
Output is correct |
| 18 |
Correct |
3 ms |
384 KB |
Output is correct |
| 19 |
Correct |
2 ms |
384 KB |
Output is correct |
| 20 |
Correct |
3 ms |
384 KB |
Output is correct |
| 21 |
Correct |
4 ms |
768 KB |
Output is correct |
| 22 |
Correct |
3 ms |
768 KB |
Output is correct |
| 23 |
Correct |
4 ms |
768 KB |
Output is correct |
| 24 |
Correct |
3 ms |
768 KB |
Output is correct |
| 25 |
Correct |
4 ms |
768 KB |
Output is correct |
| 26 |
Correct |
3 ms |
768 KB |
Output is correct |
| 27 |
Correct |
5 ms |
768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
512 KB |
Output is correct |
| 2 |
Correct |
4 ms |
640 KB |
Output is correct |
| 3 |
Correct |
4 ms |
640 KB |
Output is correct |
| 4 |
Correct |
4 ms |
512 KB |
Output is correct |
| 5 |
Correct |
4 ms |
640 KB |
Output is correct |
| 6 |
Correct |
3 ms |
640 KB |
Output is correct |
| 7 |
Correct |
4 ms |
640 KB |
Output is correct |
| 8 |
Correct |
3 ms |
512 KB |
Output is correct |
| 9 |
Correct |
4 ms |
640 KB |
Output is correct |
| 10 |
Correct |
4 ms |
640 KB |
Output is correct |
| 11 |
Correct |
3 ms |
512 KB |
Output is correct |
| 12 |
Correct |
3 ms |
512 KB |
Output is correct |
| 13 |
Correct |
4 ms |
512 KB |
Output is correct |
| 14 |
Correct |
3 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
512 KB |
Output is correct |
| 2 |
Correct |
4 ms |
640 KB |
Output is correct |
| 3 |
Correct |
4 ms |
640 KB |
Output is correct |
| 4 |
Correct |
4 ms |
512 KB |
Output is correct |
| 5 |
Correct |
4 ms |
640 KB |
Output is correct |
| 6 |
Correct |
3 ms |
640 KB |
Output is correct |
| 7 |
Correct |
4 ms |
640 KB |
Output is correct |
| 8 |
Correct |
3 ms |
512 KB |
Output is correct |
| 9 |
Correct |
4 ms |
640 KB |
Output is correct |
| 10 |
Correct |
4 ms |
640 KB |
Output is correct |
| 11 |
Correct |
3 ms |
512 KB |
Output is correct |
| 12 |
Correct |
3 ms |
512 KB |
Output is correct |
| 13 |
Correct |
4 ms |
512 KB |
Output is correct |
| 14 |
Correct |
3 ms |
640 KB |
Output is correct |
| 15 |
Correct |
213 ms |
18828 KB |
Output is correct |
| 16 |
Correct |
217 ms |
19156 KB |
Output is correct |
| 17 |
Correct |
266 ms |
20056 KB |
Output is correct |
| 18 |
Correct |
79 ms |
17640 KB |
Output is correct |
| 19 |
Correct |
168 ms |
18504 KB |
Output is correct |
| 20 |
Correct |
212 ms |
19040 KB |
Output is correct |
| 21 |
Correct |
205 ms |
19048 KB |
Output is correct |
| 22 |
Correct |
223 ms |
20320 KB |
Output is correct |
| 23 |
Correct |
232 ms |
20932 KB |
Output is correct |
| 24 |
Correct |
302 ms |
20596 KB |
Output is correct |
| 25 |
Correct |
318 ms |
20192 KB |
Output is correct |
| 26 |
Correct |
175 ms |
18912 KB |
Output is correct |
| 27 |
Correct |
157 ms |
18408 KB |
Output is correct |
| 28 |
Correct |
323 ms |
20320 KB |
Output is correct |
| 29 |
Correct |
301 ms |
19936 KB |
Output is correct |
| 30 |
Correct |
164 ms |
18536 KB |
Output is correct |
| 31 |
Correct |
291 ms |
20216 KB |
Output is correct |
| 32 |
Correct |
249 ms |
20192 KB |
Output is correct |
| 33 |
Correct |
338 ms |
20420 KB |
Output is correct |
| 34 |
Correct |
293 ms |
20448 KB |
Output is correct |
| 35 |
Correct |
160 ms |
18272 KB |
Output is correct |
| 36 |
Correct |
69 ms |
18540 KB |
Output is correct |
| 37 |
Correct |
260 ms |
21064 KB |
Output is correct |
| 38 |
Correct |
304 ms |
20164 KB |
Output is correct |
| 39 |
Correct |
308 ms |
20348 KB |
Output is correct |
