# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
17290 | 2015-11-12T17:14:30 Z | erdemkiraz | 정렬하기 (IOI15_sorting) | C++ | 638 ms | 17752 KB |
#include <bits/stdc++.h> using namespace std; #define type(x) __typeof((x).begin()) #define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++) typedef long long ll; typedef pair < int, int > ii; const int inf = 1e9 + 333; const ll linf = 1e18 + inf; #include "sorting.h" const int N = 2e5 + 5; int n, m; int s[N], a[N], h[N], w[N], p[N]; ii XY[N]; void swp(int x, int y) { int X = a[x]; int Y = a[y]; swap(w[X], w[Y]); swap(a[x], a [y]); } bool f(int x, int P[], int Q[]) { for(int i = 0; i < n; i++) { p[i] = i; } for(int i = 0; i < x; i++) { swap(p[XY[i].first], p[XY[i].second]); } for(int i = 0; i < n; i++) { w[s[i]] = i; a[i] = s[p[i]]; } memset(h, 0, sizeof(h)); int res = n, sz = 0; vector < int > v; vector < ii > ans; for(int i = 0; i < n; i++) { if(!h[i]) { res--; int x = i; v.clear(); do{ v.push_back(x); h[x] = 1; x = a[x]; }while(x != i); for(int it = (int) v.size() - 1; it >= 1; it--) { int x = v[0]; int y = v[it]; ans.push_back(ii(a[x], a[y])); } } } for(int i = 0; i < n; i++) a[i] = s[i]; if(res <= x) { for(int it = 0; it < ans.size(); it++) { swp(XY[it].first, XY[it].second); P[sz] = w[ans[it].first]; Q[sz] = w[ans[it].second]; sz++; swp(w[ans[it].first], w[ans[it].second]); } while(sz < x) { P[sz] = 0; Q[sz] = 0; sz++; } return 1; } return 0; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N; m = M; for(int i = 0; i < n; i++) s[i] = S[i]; for(int i = 0; i < m; i++) { XY[i] = ii(X[i], Y[i]); } int l = 0, r = n - 1; while(l < r) { int m = (l + r) >> 1; if(f(m, P, Q)) r = m; else l = m + 1; } f(l, P, Q); return l; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1152 KB | Output is correct |
2 | Correct | 4 ms | 1152 KB | Output is correct |
3 | Correct | 4 ms | 1152 KB | Output is correct |
4 | Correct | 4 ms | 1152 KB | Output is correct |
5 | Correct | 3 ms | 1280 KB | Output is correct |
6 | Correct | 3 ms | 1152 KB | Output is correct |
7 | Correct | 3 ms | 1152 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1152 KB | Output is correct |
2 | Correct | 4 ms | 1152 KB | Output is correct |
3 | Correct | 4 ms | 1152 KB | Output is correct |
4 | Correct | 4 ms | 1152 KB | Output is correct |
5 | Correct | 3 ms | 1280 KB | Output is correct |
6 | Correct | 3 ms | 1152 KB | Output is correct |
7 | Correct | 3 ms | 1152 KB | Output is correct |
8 | Correct | 3 ms | 1152 KB | Output is correct |
9 | Correct | 3 ms | 1152 KB | Output is correct |
10 | Correct | 3 ms | 1152 KB | Output is correct |
11 | Correct | 4 ms | 1152 KB | Output is correct |
12 | Correct | 4 ms | 1152 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1152 KB | Output is correct |
2 | Correct | 4 ms | 1152 KB | Output is correct |
3 | Correct | 4 ms | 1280 KB | Output is correct |
4 | Correct | 3 ms | 1152 KB | Output is correct |
5 | Correct | 3 ms | 1152 KB | Output is correct |
6 | Correct | 3 ms | 1152 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1152 KB | Output is correct |
2 | Correct | 4 ms | 1152 KB | Output is correct |
3 | Correct | 4 ms | 1152 KB | Output is correct |
4 | Correct | 4 ms | 1152 KB | Output is correct |
5 | Correct | 3 ms | 1280 KB | Output is correct |
6 | Correct | 3 ms | 1152 KB | Output is correct |
7 | Correct | 3 ms | 1152 KB | Output is correct |
8 | Correct | 3 ms | 1152 KB | Output is correct |
9 | Correct | 3 ms | 1152 KB | Output is correct |
10 | Correct | 3 ms | 1152 KB | Output is correct |
11 | Correct | 4 ms | 1152 KB | Output is correct |
12 | Correct | 4 ms | 1152 KB | Output is correct |
13 | Correct | 3 ms | 1152 KB | Output is correct |
14 | Correct | 4 ms | 1152 KB | Output is correct |
15 | Correct | 4 ms | 1280 KB | Output is correct |
16 | Correct | 3 ms | 1152 KB | Output is correct |
17 | Correct | 3 ms | 1152 KB | Output is correct |
18 | Correct | 3 ms | 1152 KB | Output is correct |
19 | Correct | 4 ms | 1152 KB | Output is correct |
20 | Correct | 3 ms | 1152 KB | Output is correct |
21 | Correct | 5 ms | 1408 KB | Output is correct |
22 | Correct | 4 ms | 1408 KB | Output is correct |
23 | Correct | 5 ms | 1452 KB | Output is correct |
24 | Correct | 4 ms | 1408 KB | Output is correct |
25 | Correct | 4 ms | 1408 KB | Output is correct |
26 | Correct | 5 ms | 1408 KB | Output is correct |
27 | Correct | 4 ms | 1408 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 1280 KB | Output is correct |
2 | Correct | 5 ms | 1280 KB | Output is correct |
3 | Correct | 5 ms | 1280 KB | Output is correct |
4 | Correct | 5 ms | 1280 KB | Output is correct |
5 | Correct | 5 ms | 1280 KB | Output is correct |
6 | Correct | 5 ms | 1280 KB | Output is correct |
7 | Correct | 1 ms | 1280 KB | Output is correct |
8 | Correct | 5 ms | 1408 KB | Output is correct |
9 | Correct | 6 ms | 1408 KB | Output is correct |
10 | Correct | 5 ms | 1280 KB | Output is correct |
11 | Correct | 6 ms | 1280 KB | Output is correct |
12 | Correct | 5 ms | 1408 KB | Output is correct |
13 | Correct | 5 ms | 1280 KB | Output is correct |
14 | Correct | 4 ms | 1280 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 1280 KB | Output is correct |
2 | Correct | 5 ms | 1280 KB | Output is correct |
3 | Correct | 5 ms | 1280 KB | Output is correct |
4 | Correct | 5 ms | 1280 KB | Output is correct |
5 | Correct | 5 ms | 1280 KB | Output is correct |
6 | Correct | 5 ms | 1280 KB | Output is correct |
7 | Correct | 1 ms | 1280 KB | Output is correct |
8 | Correct | 5 ms | 1408 KB | Output is correct |
9 | Correct | 6 ms | 1408 KB | Output is correct |
10 | Correct | 5 ms | 1280 KB | Output is correct |
11 | Correct | 6 ms | 1280 KB | Output is correct |
12 | Correct | 5 ms | 1408 KB | Output is correct |
13 | Correct | 5 ms | 1280 KB | Output is correct |
14 | Correct | 4 ms | 1280 KB | Output is correct |
15 | Correct | 442 ms | 16088 KB | Output is correct |
16 | Correct | 502 ms | 16372 KB | Output is correct |
17 | Correct | 556 ms | 16784 KB | Output is correct |
18 | Correct | 88 ms | 12396 KB | Output is correct |
19 | Correct | 302 ms | 13728 KB | Output is correct |
20 | Correct | 373 ms | 16376 KB | Output is correct |
21 | Correct | 375 ms | 16124 KB | Output is correct |
22 | Correct | 563 ms | 17064 KB | Output is correct |
23 | Correct | 550 ms | 17752 KB | Output is correct |
24 | Correct | 638 ms | 17028 KB | Output is correct |
25 | Correct | 468 ms | 16940 KB | Output is correct |
26 | Correct | 362 ms | 15452 KB | Output is correct |
27 | Correct | 325 ms | 13892 KB | Output is correct |
28 | Correct | 502 ms | 16808 KB | Output is correct |
29 | Correct | 606 ms | 15888 KB | Output is correct |
30 | Correct | 295 ms | 13608 KB | Output is correct |
31 | Correct | 593 ms | 16212 KB | Output is correct |
32 | Correct | 475 ms | 16904 KB | Output is correct |
33 | Correct | 517 ms | 16892 KB | Output is correct |
34 | Correct | 519 ms | 16420 KB | Output is correct |
35 | Correct | 280 ms | 13680 KB | Output is correct |
36 | Correct | 64 ms | 12024 KB | Output is correct |
37 | Correct | 456 ms | 17476 KB | Output is correct |
38 | Correct | 350 ms | 17008 KB | Output is correct |
39 | Correct | 441 ms | 17024 KB | Output is correct |