제출 #391562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391562		usachevd0	정렬하기 (IOI15_sorting)	C++14	100 / 100	203 ms	20320 KiB

sorting

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }
void debug_out() { cerr << endl; }
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); }
template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; }
#ifdef DEBUG
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) { for (auto x : v) stream << x << ' '; return stream; }
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; }

int findSwapPairs(int n, int* s, int m, int* X, int* Y, int* ansX, int* ansY) {
  auto good = [&](int k, bool restore) {
    vector<int> p(s, s + n);
    for (int i = 0; i < k; ++i) {
      swap(p[X[i]], p[Y[i]]);
    }
    vector<char> used(n, false);
    int ptr = 0;
    vector<int> u(k), v(k);
    for (int x = 0; x < n; ++x) {
      if (!used[x]) {
        int y = x;
        do {
          used[y] = true;
          if (p[y] != x) {
            if (ptr == k) {
              return false;
            }
            u[ptr] = y;
            v[ptr] = p[y];
            ++ptr;
          }
          y = p[y];
        } while (y != x);
      }
    }
    if (restore) {
      vector<int> p(s, s + n);
      vector<int> ip(n);
      for (int x = 0; x < n; ++x) {
        ip[p[x]] = x;
      }
      for (int i = 0; i < k; ++i) {
        int a = p[X[i]];
        int b = p[Y[i]];
        swap(p[X[i]], p[Y[i]]);
        swap(ip[a], ip[b]);

        int k = ip[u[i]];
        int l = ip[v[i]];
        ansX[i] = k;
        ansY[i] = l;
        swap(p[k], p[l]);
        swap(ip[u[i]], ip[v[i]]);
      }
    }
    return true;
  };

  int vl = -1;
  int vr = m;
  while (vr - vl > 1) {
    int vm = (vl + vr) >> 1;
    if (good(vm, false)) {
      vr = vm;
    } else {
      vl = vm;
    }
  }
  good(vr, true);
  return vr;
}

#ifdef DEBUG
signed main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  int* s = new int[n];
  for (int x = 0; x < n; ++x) {
    cin >> s[x];
  }
  int m;
  cin >> m;
  int* x = new int[m];
  int* y = new int[m];
  for (int i = 0; i < m; ++i) {
    cin >> x[i] >> y[i];
  }
  int* p = new int[m];
  int* q = new int[m];
  int R = findSwapPairs(n, s, m, x, y, p, q);
  cout << R << '\n';
  for (int i = 0; i < R; ++i) {
    cout << p[i] << ' ' << q[i] << '\n';
  }
    
  return 0;
}
#endif

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

sorting.cpp: In lambda function:
sorting.cpp:59:21: warning: declaration of 'p' shadows a previous local [-Wshadow]
   59 |       vector<int> p(s, s + n);
      |                     ^
sorting.cpp:34:17: note: shadowed declaration is here
   34 |     vector<int> p(s, s + n);
      |                 ^
sorting.cpp:70:13: warning: declaration of 'int k' shadows a parameter [-Wshadow]
   70 |         int k = ip[u[i]];
      |             ^
sorting.cpp:33:23: note: shadowed declaration is here
   33 |   auto good = [&](int k, bool restore) {
      |                   ~~~~^

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26