제출 #726592

#제출 시각아이디문제언어결과실행 시간메모리
726592becaido정렬하기 (IOI15_sorting)C++17
100 / 100
161 ms20224 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,popcnt,sse4,abm") #include <bits/stdc++.h> using namespace std; #ifndef WAIMAI #include "sorting.h" #endif #ifdef WAIMAI #define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE) void dout() {cout << '\n';} template<typename T, typename...U> void dout (T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);} #else #define debug(...) 7122 #endif #define ll long long #define Waimai ios::sync_with_stdio(false), cin.tie(0) #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++) #define pb emplace_back const int SIZE = 2e5 + 5; int n; int a[SIZE], p[SIZE]; bool vs[SIZE]; bool ok(int r, int S[], int X[], int Y[]) { FOR (i, 0, n - 1) a[i] = S[i], vs[i] = 0; FOR (i, 0, r - 1) swap(a[X[i]], a[Y[i]]); int cnt = n; FOR (i, 0, n - 1) if (!vs[i]) { cnt--; for (int cur = i; !vs[cur]; cur = a[cur]) vs[cur] = 1; } return cnt <= r; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N; int l = 0, r = M; while (l < r) { int mid = (l + r) / 2; if (ok(mid, S, X, Y)) r = mid; else l = mid + 1; } FOR (i, 0, n - 1) a[i] = S[i], vs[i] = 0; FOR (i, 0, r - 1) swap(a[X[i]], a[Y[i]]); int sz = 0; FOR (i, 0, n - 1) if (!vs[i]) { int last = -1, cur = i; while (!vs[cur]) { vs[cur] = 1; if (last != -1) P[sz] = last, Q[sz] = cur, sz++; last = cur; cur = a[cur]; } } while (sz < r) P[sz] = Q[sz] = 0, sz++; FOR (i, 0, n - 1) p[S[i]] = i; FOR (i, 0, r - 1) { swap(p[S[X[i]]], p[S[Y[i]]]); swap(S[X[i]], S[Y[i]]); int a = P[i], b = Q[i]; P[i] = p[a], Q[i] = p[b]; swap(p[S[P[i]]], p[S[Q[i]]]); swap(S[P[i]], S[Q[i]]); } return r; } /* in1 5 4 3 2 1 0 6 0 1 1 2 2 3 3 4 0 1 1 2 out1 3 0 4 1 3 3 4 in2 5 3 0 4 2 1 5 1 1 4 0 2 3 1 4 0 4 out2 3 1 4 4 2 2 2 */ #ifdef WAIMAI int main() { int N, M; cin >> N; int *S = (int*)malloc(sizeof(int) * (unsigned int)N); for (int i = 0; i < N; ++i) cin >> S[i]; cin >> M; int *X = (int*)malloc(sizeof(int) * (unsigned int)M), *Y = (int*)malloc(sizeof(int) * (unsigned int)M); for (int i = 0; i < M; ++i) { cin >> X[i]; cin >> Y[i]; } int *P = (int*)malloc(sizeof(int) * (unsigned int)M), *Q = (int*)malloc(sizeof(int) * (unsigned int)M); int ans = findSwapPairs(N, S, M, X, Y, P, Q); cout << ans << '\n'; for (int i = 0; i < ans; ++i) cout << P[i] << ' ' << Q[i] << '\n'; return 0; } #endif

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

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:66:13: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   66 |         int a = P[i], b = Q[i];
      |             ^
sorting.cpp:27:5: note: shadowed declaration is here
   27 | int a[SIZE], p[SIZE];
      |     ^
#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...