제출 #707794

#제출 시각아이디문제언어결과실행 시간메모리
707794baojiaopisu정렬하기 (IOI15_sorting)C++14
74 / 100
1041 ms23084 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]; 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; // cout << a[i] << " "; } // cout << endl; 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 = ans; i >= 1; i--) { if(op.empty()) break; int r = op.back().fi, t = op.back().se; for(int i = 1; i <= n; i++) c[i] = i; for(int j = i + 1; j <= ans; j++) { swap(c[x[j]], c[y[j]]); swap(c[P[j] + 1], c[P[j] + 1]); } r = c[r], t = c[t]; P[i] = r - 1; Q[i] = t - 1; op.pop_back(); } for(int i = 0; i < m; i++) { P[i] = P[i + 1]; Q[i] = Q[i + 1]; } 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:140:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
  140 |     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:141:13: warning: declaration of 'y' shadows a global declaration [-Wshadow]
  141 |         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:150:13: warning: declaration of 'r' shadows a previous local [-Wshadow]
  150 |         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;
      |                ^
sorting.cpp:151:17: warning: declaration of 'i' shadows a previous local [-Wshadow]
  151 |         for(int i = 1; i <= n; i++) c[i] = i;
      |                 ^
sorting.cpp:148:13: note: shadowed declaration is here
  148 |     for(int i = ans; i >= 1; i--) {
      |             ^
#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...