Submission #802527

#	Time	Username	Problem	Language	Result	Execution time	Memory
802527		erray	Sorting (IOI15_sorting)	C++17	100 / 100	219 ms	29324 KiB

sorting

#include "sorting.h"\

#include<bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/codes/ioi15_d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

template<typename T> 
vector<T> inverse_fuck(T* a, int N) {
  vector<T> res(N);
  for (int i = 0; i < N; ++i) {
    res[i] = a[i];
  }
  return res;
}

int findSwapPairs(int N, int __S[], int M, int __X[], int __Y[], int __P[], int __Q[]) {
  auto S = inverse_fuck(__S, N);
  auto X = inverse_fuck(__X, M);
  auto Y = inverse_fuck(__Y, M);
  vector<int> P(M), Q(M);
  debug(X, Y);
  auto Check = [&](int m) {
    debug(m);
    auto a = S;
    for (int i = 0; i < m; ++i) {
      swap(a[X[i]], a[Y[i]]);
    }
    debug(a);
    vector<bool> vis(N);
    vector<array<int, 2>> swaps;
    for (int i = 0; i < N; ++i) {
      if (vis[i]) {
        continue;
      }
      int v = i;
      while (a[v] != i) {
        swaps.push_back({v, a[v]});
        v = a[v];
        vis[v] = true;
      }
    }
    debug(swaps);
    int moves = int(swaps.size()); 
    if (moves > m) {
      return false;
    }
    a = S;
    vector<int> inv(N);
    for (int i = 0; i < N; ++i) {
      inv[a[i]] = i;
    }
    auto Move = [&](int x, int y) {
      swap(inv[a[x]], inv[a[y]]);
      swap(a[x], a[y]);
    };
    for (int i = 0; i < moves; ++i) {
      Move(X[i], Y[i]);
      P[i] = inv[swaps[i][0]];
      Q[i] = inv[swaps[i][1]];
      Move(P[i], Q[i]);
    }   
    while (moves < m) {
      P[moves] = Q[moves] = 0;
      ++moves;
    }
    return true;
  };  
  int low = 0, high = M;
  while (low < high) {
    int mid = (low + high) >> 1;
    if (!Check(mid)) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  debug(low);
  int ans = !Check(low) ? -1 : low;
  if (ans != -1) {
    for (int i = 0; i < ans; ++i) {
      __P[i] = P[i];
      __Q[i] = Q[i];
      swap(S[X[i]], S[Y[i]]);
      debug(S);
      swap(S[P[i]], S[Q[i]]);
      debug(S);
    }
  }
  return ans;
}

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