제출 #785328

#제출 시각아이디문제언어결과실행 시간메모리
785328NothingXD정렬하기 (IOI15_sorting)C++17
100 / 100
158 ms17076 KiB
#include "sorting.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef complex<ld> point; void debug_out(){cerr << endl;} template<typename Head, typename... Tail> void debug_out(Head H, Tail... T){ cout << H << " "; debug_out(T...); } #define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__) #define F first #define S second #define all(x) x.begin(), x.end() #define MP(x, y) make_pair(x, y) const int maxn = 2e5 + 10; int n, a[maxn], b[maxn], idx[maxn], x[3*maxn], y[3*maxn]; bool vis[maxn]; bool check(int k){ for (int i = 0; i < n; i++) b[i] = a[i]; for (int i = 0; i < k; i++){ swap(b[x[i]], b[y[i]]); } memset(vis, false, sizeof vis); int cnt = 0; for (int i = 0; i < n; i++){ if (!vis[i]) cnt++; int x = i; while(!vis[x]){ vis[x] = true; x = b[x]; } } return n - cnt <= k; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N; for (int i = 0; i < n; i++){ a[i] = S[i]; idx[a[i]] = i; } for (int i = 0; i < M; i++){ x[i] = X[i]; y[i] = Y[i]; } int l = -1, r = M; while(l + 1 < r){ int mid = (l+r) >> 1; if (check(mid)) r = mid; else l = mid; } for (int i = 0; i < n; i++){ b[i] = a[i]; } for (int i = 0; i < r; i++){ swap(b[x[i]], b[y[i]]); } vector<pii> swp; memset(vis, false, sizeof vis); for (int i = 0; i < n; i++){ int x = i; vector<int> ver; while(!vis[x]){ ver.push_back(x); vis[x] = true; x = b[x]; } for (int j = 1; j < ver.size(); j++){ swp.push_back(MP(ver[j-1], ver[j])); } } for (int i = 0; i < r; i++){ swap(a[x[i]], a[y[i]]); swap(idx[a[x[i]]], idx[a[y[i]]]); if (i < swp.size()){ P[i] = idx[swp[i].F]; Q[i] = idx[swp[i].S]; } else{ P[i] = Q[i] = 0; } swap(a[P[i]], a[Q[i]]); swap(idx[a[P[i]]], idx[a[Q[i]]]); } return r; }

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

sorting.cpp: In function 'bool check(int)':
sorting.cpp:40:7: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   40 |   int x = i;
      |       ^
sorting.cpp:28:37: note: shadowed declaration is here
   28 | int n, a[maxn], b[maxn], idx[maxn], x[3*maxn], y[3*maxn];
      |                                     ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:77:7: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   77 |   int x = i;
      |       ^
sorting.cpp:28:37: note: shadowed declaration is here
   28 | int n, a[maxn], b[maxn], idx[maxn], x[3*maxn], y[3*maxn];
      |                                     ^
sorting.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int j = 1; j < ver.size(); j++){
      |                   ~~^~~~~~~~~~~~
sorting.cpp:92:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   if (i < swp.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...