제출 #124567

#제출 시각아이디문제언어결과실행 시간메모리
124567RockyB정렬하기 (IOI15_sorting)C++14
74 / 100
195 ms16436 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)5e5 + 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 pos[n]; rep(i, 0, n) { pos[b[i]] = i; } int cnt = 0; rep(i, 0, n) { if (b[i] != i) { swap(b[i], b[pos[i]]); swap(pos[b[i]], pos[b[pos[i]]]); ++cnt; } } 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 = 0, 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); // opt len found rep(i, 0, res) { P[i] = Q[i] = 0; } rep(i, 0, n) { b[i] = a[i]; } rep(i, 0, res) { swap(b[x[i]], b[y[i]]); } vector <int> st; int go[n], pos[n], fnd[n]; rep(i, 0, n) { go[b[i]] = i; pos[i] = b[i]; } rep(i, 0, n) { if (go[i] != i) st.pb(i); } int ptr = 0; if (!sz(st)) { ptr = 0; P[ptr] = 0; Q[ptr] = 0; return res; } swap(a[X[ptr]], a[Y[ptr]]); rep(i, 0, n) { fnd[a[i]] = i; } for (auto x : st) { if (go[x] == x) { continue; } /* rep(i, 0, n) { cerr << a[i] << ' '; } cerr << nl; rep(i, 0, n) { cerr << go[i] << ' '; } cerr << nl; */ int p1 = fnd[x]; //cerr << a[p1] << ' ' << x << nl; rep(i, 0, n) { i = pos[x]; if (go[i] == x) { int p2 = fnd[i]; //cerr << a[p2] << ' ' << i << nl; P[ptr] = p1; Q[ptr] = p2; swap(go[x], go[i]); swap(pos[go[x]], pos[go[i]]); swap(fnd[x], fnd[i]); swap(a[p1], a[p2]); ptr++; break; } break; } /* cerr << " -> " << x << nl; rep(i, 0, n) cerr << a[i] << ' '; cerr << nl; rep(i, 0, n) cerr << go[i] << ' '; cerr << nl << nl;*/ if (ptr < m) { swap(a[X[ptr]], a[Y[ptr]]); swap(fnd[a[X[ptr]]], fnd[a[Y[ptr]]]); ///// don't use/// swap(go[a[X[ptr]]], go[a[Y[ptr]]]); } } return res; } #ifdef IOI2018 namespace gen { void gen() { int N, M; N = rand() % 5 + 1; int *S = (int*)malloc(sizeof(int) * (unsigned int)N); for (int i = 0; i < N; ++i) S[i] = i; random_shuffle(S, S + N); printf ("%d\n", N); fflush(stdout); int A[N]; for (int i = 0; i < N; i++) { A[i] = S[i]; printf ("%d ", A[i]); } printf ("\n"); fflush(stdout); M = rand() % 5 + 1; printf ("%d\n", M); fflush(stdout); int *X = (int*)malloc(sizeof(int) * (unsigned int)M), *Y = (int*)malloc(sizeof(int) * (unsigned int)M); for (int i = 0; i < M; ++i) { X[i] = rand() % N; Y[i] = rand() % N; printf ("%d %d\n", X[i], Y[i]); fflush(stdout); } 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); printf("%d\n", ans); fflush(stdout); //assert(ans <= 30 * N); for (int i = 0; i < ans; ++i) { if (i < M) swap(A[X[i]], A[Y[i]]); swap(A[P[i]], A[Q[i]]); } for (int i = 0; i < N; i++) { //assert(A[i] == i); printf("%d ", A[i]); } for (int i = 0; i < N; i++) { assert(A[i] == i); //printf("%d ", A[i]); } } } int main() { rep(i, 1, 1000) { printf ("Case: %d\n", i); fflush(stdout); srand(i); gen :: gen(); printf ("\n"); fflush(stdout); } } #endif

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

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:108:12: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  for (auto x : st) {
            ^
sorting.cpp:30:23: note: shadowed declaration is here
 int a[MAXN], b[MAXN], x[MAXN], y[MAXN];
                       ^
#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...