제출 #124430

#제출 시각아이디문제언어결과실행 시간메모리
124430RockyB정렬하기 (IOI15_sorting)C++17
0 / 100
4 ms632 KiB
/// In The Name Of God #include "sorting.h" #include <bits/stdc++.h> #define f first #define s second #define pb push_back #define pp pop_back #define mp make_pair #define sz(x) (int)x.size() #define sqr(x) ((x) * 1ll * (x)) #define all(x) x.begin(), x.end() #define rep(i, l, r) for (int i = (l); i < (r); i++) #define per(i, l, r) for (int i = (l); i >= (r); i--) #define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0); #define nl '\n' #define ioi exit(0); const int MAXN = (int)2e5 + 7; using namespace std; int n, m; int a[MAXN], b[MAXN], x[MAXN], y[MAXN]; bool check(int len) { rep(i, 0, n) { b[i] = a[i]; } rep(i, 0, len) { swap(b[x[i]], b[y[i]]); } int cnt = 0; rep(i, 0, n) { if (b[i] != i) { ++cnt; swap(b[i], b[b[i]]); } } if (cnt > len) return 0; return 1; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { { n = N; m = M; rep(i, 0, n) { a[i] = S[i]; } rep(i, 0, m) { x[i] = X[i]; y[i] = Y[i]; } } // copying int l = 1, r = M, res = -1; while (l <= r) { int mid = (l + r) >> 1; if (check(mid)) res = mid, r = mid - 1; else l = mid + 1; } assert(res != -1); rep(i, 0, n) { b[i] = a[i]; } rep(i, 0, res) { swap(b[x[i]], b[y[i]]); } vector < pair <int, int> > need; rep(i, 0, n) { if (b[i] != i) { need.pb({b[i], b[b[i]]}); swap(b[i], b[b[i]]); } } rep(i, 0, res) { if (!sz(need)) { swap(S[X[i]], S[Y[i]]); P[i] = 0; Q[i] = 0; } else { int v1 = need.back().f, v2 = need.back().s; need.pop_back(); swap(S[X[i]], S[Y[i]]); int p1 = -1, p2; rep(j, 0, n) { if (S[j] == v1 || S[j] == v2) { if (p1 == -1) p1 = j; p2 = j; } } P[i] = p1; Q[i] = p2; swap(S[p1], S[p2]); } } return res; } #ifdef IOI2018 int main() { if (0) { freopen ("sorting.in", "r", stdin); int n, m; cin >> n; int s[n], c[n]; for (int i = 0; i < n; i++) cin >> s[i], c[i] = s[i]; cin >> m; int x[m], y[m]; for (int i = 0; i < m; i++) cin >> x[i] >> y[i]; int p[m], q[m]; int ans = findSwapPairs(n, s, m, x, y, p, q); for (int i = 0; i < ans; i++) { swap(c[x[i]], c[y[i]]); swap(c[p[i]], c[q[i]]); } for (int i = 0; i < n; i++) { cout << c[i] << ' '; } ioi } srand(time(0)); for (int T = 5; T <= 100; T++) { srand(T); int n = rand() % 5 + 1, m = 30 * n; int s[n], a[n], c[n]; for (int i = 0; i < n; i++) s[i] = i; random_shuffle(s, s + n); for (int i = 0; i < n; i++) a[i] = c[i] = s[i]; int x[m], y[m]; for (int i = 0; i < m; i++) { x[i] = 0, y[i] = 1; } int p[m], q[m]; int ans = findSwapPairs(n, s, m, x, y, p, q); for (int i = 0; i < ans; i++) { swap(c[x[i]], c[y[i]]); swap(c[p[i]], c[q[i]]); } bool bad = 0; for (int i = 0; i < n; i++) { if (c[i] != i) bad = 1; } if (bad == 1) { cout << n << nl; for (int i = 0; i < n; i++) cout << a[i] << ' '; cout << nl; cout << m << nl; for (int i = 0; i < m; i++) { cout << x[i] << ' ' << y[i] << nl; } ioi assert(0); } } } #endif

컴파일 시 표준 에러 (stderr) 메시지

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:100:9: warning: 'p2' may be used uninitialized in this function [-Wmaybe-uninitialized]
    Q[i] = p2;
    ~~~~~^~~~
#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...