제출 #707804

#제출 시각아이디문제언어결과실행 시간메모리
707804baojiaopisu정렬하기 (IOI15_sorting)C++14
100 / 100
197 ms28416 KiB
#include "sorting.h" #include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; using pii = pair<int, int>; using pll = pair<ll, ll>; using pld = pair<ld, ld>; #define fi first #define se second #define left BAO #define right ANH #define pb push_back #define pf push_front #define mp make_pair #define ins insert #define btpc __builtin_popcount #define btclz __builtin_clz #define sz(x) (int)(x.size()); #define all(x) x.begin(), x.end() #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1}; int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1}; int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1}; template<class X, class Y> bool minimize(X &x, const Y &y) { if (x > y) { x = y; return true; } return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { if (x < y) { x = y; return true; } return false; } const int MOD = 1e9 + 7; //998244353 template<class X, class Y> void add(X &x, const Y &y) { x = (x + y); if(x >= MOD) x -= MOD; } template<class X, class Y> void sub(X &x, const Y &y) { x = (x - y); if(x < 0) x += MOD; } /* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/ const ll INF = 1e9; const int N = 2e6 + 10; int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N]; int par[N], pos[N], c[N], p[N]; int find_par(int u) { if(par[u] < 0) return u; par[u] = find_par(par[u]); return par[u]; } bool merge(int u, int v) { u = find_par(u), v = find_par(v); if(u == v) return false; if(par[u] > par[v]) swap(u, v); par[u] += par[v]; par[v] = u; return true; } int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) { for(int i = 1; i <= n; i++) { s[i] = S[i - 1] + 1; } for(int i = 1; i <= m; i++) { x[i] = X[i - 1] + 1; y[i] = Y[i - 1] + 1; } int l = 0, r = m, ans = 0; while(l <= r) { int mid = (l + r) >> 1; for(int i = 1; i <= n; i++) a[i] = s[i]; for(int i = 1; i <= mid; i++) { swap(a[x[i]], a[y[i]]); } for(int i = 1; i <= n; i++) par[i] = -1; for(int i = 1; i <= n; i++) merge(i, a[i]); int cnt = 0; for(int i = 1; i <= n; i++) { if(find_par(i) == i) ++cnt; } if((n - cnt) <= mid) { ans = mid; r = mid - 1; } else l = mid + 1; } for(int i = 1; i <= n; i++) a[i] = s[i]; for(int i = 1; i <= ans; i++) { swap(a[x[i]], a[y[i]]); } for(int i = 1; i <= n; i++) par[i] = -1; for(int i = 1; i <= n; i++) merge(i, a[i]); vector<int> q; for(int i = 1; i <= n; i++) { if(find_par(i) != i) q.pb(i); } for(int i = 1; i <= n; i++) { pos[a[i]] = i; } vector<pii> op; for(auto x : q) { int y = a[x]; op.pb(mp(pos[x], x)); swap(a[x], a[pos[x]]); pos[y] = pos[x]; pos[x] = x; } for(int i = 1; i <= n; i++) c[i] = p[i] = i; for(int i = ans; i >= 1; i--) { if(op.empty()) break; int r = op.back().fi, t = op.back().se; r = c[r], t = c[t]; P[i - 1] = r - 1; Q[i - 1] = t - 1; // swap(c[p[r]], c[p[t]]); // swap(p[r], p[t]); swap(c[p[x[i]]], c[p[y[i]]]); swap(p[x[i]], p[y[i]]); op.pop_back(); } return ans; }

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

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:90:73: warning: declaration of 'Q' shadows a global declaration [-Wshadow]
   90 | int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
      |                                                                     ~~~~^~~
sorting.cpp:73:11: note: shadowed declaration is here
   73 | int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N];
      |           ^
sorting.cpp:90:64: warning: declaration of 'P' shadows a global declaration [-Wshadow]
   90 | int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
      |                                                            ~~~~^~~
sorting.cpp:73:5: note: shadowed declaration is here
   73 | int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N];
      |     ^
sorting.cpp:90:55: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
   90 | int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
      |                                                   ~~~~^~~
sorting.cpp:73:35: note: shadowed declaration is here
   73 | int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N];
      |                                   ^
sorting.cpp:90:46: warning: declaration of 'X' shadows a global declaration [-Wshadow]
   90 | int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
      |                                          ~~~~^~~
sorting.cpp:73:29: note: shadowed declaration is here
   73 | int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N];
      |                             ^
sorting.cpp:90:30: warning: declaration of 'S' shadows a global declaration [-Wshadow]
   90 | int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
      |                          ~~~~^~~
sorting.cpp:73:47: note: shadowed declaration is here
   73 | int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N];
      |                                               ^
sorting.cpp:138:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  138 |     for(auto x : q) {
      |              ^
sorting.cpp:73:17: note: shadowed declaration is here
   73 | int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N];
      |                 ^
sorting.cpp:139:13: warning: declaration of 'y' shadows a global declaration [-Wshadow]
  139 |         int y = a[x];
      |             ^
sorting.cpp:73:23: note: shadowed declaration is here
   73 | int P[N], Q[N], x[N], y[N], X[N], Y[N], s[N], S[N], a[N];
      |                       ^
sorting.cpp:149:13: warning: declaration of 'r' shadows a previous local [-Wshadow]
  149 |         int r = op.back().fi, t = op.back().se;
      |             ^
sorting.cpp:100:16: note: shadowed declaration is here
  100 |     int l = 0, r = m, ans = 0;
      |                ^
#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...