Submission #879236

#	Time	Username	Problem	Language	Result	Execution time	Memory
879236		NeroZein	Sorting (IOI15_sorting)	C++17	100 / 100	215 ms	19312 KiB

sorting

#include "sorting.h"
#include "bits/stdc++.h"

using namespace std; 

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
  if (is_sorted(S, S + N)) {
    return 0; 
  }
  auto check = [&](int mid) {
    vector<int> finalArray(N);
    for (int i = 0; i < N; ++i) {
      finalArray[i] = S[i];
    }
    for (int i = 0; i < mid; ++i) {
      swap(finalArray[X[i]], finalArray[Y[i]]); 
    }
    vector<int> next(N);
    vector<pair<int, int>> swaps;
    for (int i = 0; i < N; ++i) {
      next[i] = finalArray[i];
    }
    vector<bool> vis(N);
    for (int i = 0; i < N; ++i) {
      if (vis[i] || next[i] == i) continue; 
      int cur = i, nxt = next[i];
      vis[i] = true; 
      while (nxt != i) {
        vis[nxt] = true; 
        swaps.emplace_back(cur, nxt);
        cur = nxt;
        nxt = next[cur]; 
      }
    }
    vector<int> idx(N); 
    vector<int> currentArray(N);
    for (int i = 0; i < N; ++i) {
      idx[S[i]] = i; 
      currentArray[i] = S[i]; 
    }
    auto swapp = [&](int x, int y) {
      swap(idx[x], idx[y]); 
      swap(currentArray[idx[x]], currentArray[idx[y]]); 
    };
    for (int i = 0; i < (int) swaps.size(); ++i) {
      int x = currentArray[X[i]], y = currentArray[Y[i]];
      swapp(x, y); 
      auto [p, q] = swaps[i];
      P[i] = idx[p], Q[i] = idx[q]; 
      swapp(p, q); 
    }
    for (int i = (int) swaps.size(); i < mid; ++i) {
      P[i] = Q[i] = 0; 
    }
    return (int) swaps.size() <= mid; 
  };
  int l = 0, r = M; 
  while (l < r) {
    int mid = (l + r) / 2;
    if (check(mid)) {
      r = mid; 
    } else {
      l = mid + 1; 
    }
  }
  check(l); 
  return l; 
}

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