# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
785473 | 2023-07-17T09:25:47 Z | Sohsoh84 | 정렬하기 (IOI15_sorting) | C++17 | 205 ms | 21500 KB |
#include "sorting.h" #include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << ": " << x << endl; #define sep ' ' const int MAXN = 1e6 + 10; int X[MAXN], Y[MAXN], n, m, ans_A[MAXN], ans_B[MAXN], T[MAXN], P[MAXN], S[MAXN], ind[MAXN]; inline void check(set<int>& st, int x) { if (st.find(x) != st.end()) st.erase(x); if (P[x] != x) st.insert(x); } inline bool solve(int m) { // P: jaye mellat too jaygasht nahayii baad swap ha for (int i = 0; i < n; i++) T[i] = S[i]; for (int i = 0; i <= m; i++) swap(T[X[i]], T[Y[i]]); for (int i = 0; i < n; i++) P[T[i]] = i; for (int i = 0; i < n; i++) { T[i] = S[i]; ind[S[i]] = i; } vector<int> vec; for (int i = 0; i < n; i++) if (P[i] != i) vec.push_back(i); for (int i = 0; i <= m; i++) { swap(T[X[i]], T[Y[i]]); ind[T[X[i]]] = X[i]; ind[T[Y[i]]] = Y[i]; while (!vec.empty() && P[vec.back()] == vec.back()) vec.pop_back(); if (vec.empty()) ans_A[i] = ans_B[i] = 0; else { int e = vec.back(); ans_A[i] = ind[e]; ans_B[i] = ind[P[e]]; int a = e, b = P[e]; swap(P[e], P[P[e]]); vec.push_back(a); vec.push_back(b); } swap(T[ans_A[i]], T[ans_B[i]]); ind[T[ans_A[i]]] = ans_A[i]; ind[T[ans_B[i]]] = ans_B[i]; } while (!vec.empty() && P[vec.back()] == vec.back()) vec.pop_back(); return vec.empty(); } 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++) X[i] = X_[i], Y[i] = Y_[i]; bool flag = true; for (int i = 0; i < n; i++) if (S[i] != i) flag = false; if (flag) return 0; int l = 0, r = m - 1; while (l < r) { int mid = (l + r) >> 1; if (solve(mid)) r = mid; else l = mid + 1; } solve(l); for (int i = 0; i <= l; i++) P[i] = ans_A[i], Q[i] = ans_B[i]; return l + 1; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 1 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 0 ms | 212 KB | Output is correct |
9 | Correct | 1 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 1 ms | 212 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 1 ms | 340 KB | Output is correct |
17 | Correct | 1 ms | 340 KB | Output is correct |
18 | Correct | 0 ms | 340 KB | Output is correct |
19 | Correct | 0 ms | 212 KB | Output is correct |
20 | Correct | 0 ms | 340 KB | Output is correct |
21 | Correct | 2 ms | 596 KB | Output is correct |
22 | Correct | 1 ms | 596 KB | Output is correct |
23 | Correct | 2 ms | 596 KB | Output is correct |
24 | Correct | 1 ms | 604 KB | Output is correct |
25 | Correct | 1 ms | 596 KB | Output is correct |
26 | Correct | 1 ms | 596 KB | Output is correct |
27 | Correct | 2 ms | 596 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 468 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 2 ms | 468 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 2 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 468 KB | Output is correct |
8 | Correct | 2 ms | 468 KB | Output is correct |
9 | Correct | 1 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 468 KB | Output is correct |
12 | Correct | 1 ms | 468 KB | Output is correct |
13 | Correct | 1 ms | 468 KB | Output is correct |
14 | Correct | 1 ms | 468 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 468 KB | Output is correct |
2 | Correct | 1 ms | 468 KB | Output is correct |
3 | Correct | 2 ms | 468 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 468 KB | Output is correct |
6 | Correct | 2 ms | 468 KB | Output is correct |
7 | Correct | 1 ms | 468 KB | Output is correct |
8 | Correct | 2 ms | 468 KB | Output is correct |
9 | Correct | 1 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 1 ms | 468 KB | Output is correct |
12 | Correct | 1 ms | 468 KB | Output is correct |
13 | Correct | 1 ms | 468 KB | Output is correct |
14 | Correct | 1 ms | 468 KB | Output is correct |
15 | Correct | 166 ms | 19828 KB | Output is correct |
16 | Correct | 174 ms | 18364 KB | Output is correct |
17 | Correct | 191 ms | 19296 KB | Output is correct |
18 | Correct | 39 ms | 10320 KB | Output is correct |
19 | Correct | 141 ms | 19436 KB | Output is correct |
20 | Correct | 148 ms | 20028 KB | Output is correct |
21 | Correct | 145 ms | 20096 KB | Output is correct |
22 | Correct | 174 ms | 19564 KB | Output is correct |
23 | Correct | 195 ms | 19948 KB | Output is correct |
24 | Correct | 194 ms | 19696 KB | Output is correct |
25 | Correct | 190 ms | 19424 KB | Output is correct |
26 | Correct | 149 ms | 19016 KB | Output is correct |
27 | Correct | 133 ms | 17528 KB | Output is correct |
28 | Correct | 189 ms | 19444 KB | Output is correct |
29 | Correct | 176 ms | 19024 KB | Output is correct |
30 | Correct | 119 ms | 16952 KB | Output is correct |
31 | Correct | 198 ms | 19360 KB | Output is correct |
32 | Correct | 182 ms | 19344 KB | Output is correct |
33 | Correct | 190 ms | 21500 KB | Output is correct |
34 | Correct | 201 ms | 19564 KB | Output is correct |
35 | Correct | 136 ms | 19140 KB | Output is correct |
36 | Correct | 61 ms | 15904 KB | Output is correct |
37 | Correct | 205 ms | 20284 KB | Output is correct |
38 | Correct | 189 ms | 19476 KB | Output is correct |
39 | Correct | 189 ms | 19624 KB | Output is correct |