Submission #1156230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156230		aarb_.tomatexd	Sorting (IOI15_sorting)	C++20	100 / 100	80 ms	13636 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long 

int findSwapPairs(int n, int *s, int m, int *x, int *y, int *p, int *q) {
  vector<int> a(n), pos(n);
  vector<array<int, 2>> ops(m);
  auto count = [&](int k) {
    for (int i = 0; i < n; ++i) {
      a[i] = s[i];
    }
    for (int i = 0; i < k; ++i) {
      swap(a[x[i]], a[y[i]]);
    }
    for (int i = 0; i < n; ++i) {
      pos[a[i]] = i;
    }
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      if (i == a[i]) {
        continue;
      }
      int j = pos[i];
      ops[cnt++] = {a[i], a[j]};
      swap(pos[a[i]], pos[a[j]]);
      swap(a[i], a[j]);
    }
    return cnt;
  };
  int l = 0, r = m, k = m;
  while (l <= r) {
    int md = (l + r) / 2;
    if (count(md) <= md) {
      k = md;
      r = md - 1;
    } else {
      l = md + 1;
    }
  }
  auto cnt = count(k);
  for (int i = cnt; i < k; ++i) {
    ops[i] = {0, 0};
  }
  for (int i = 0; i < n; ++i) {
    pos[s[i]] = i;
  }
  auto swp = [&](int i, int j) {
    swap(pos[s[i]], pos[s[j]]);
    swap(s[i], s[j]);
  };
  for (int i = 0; i < k; ++i) {
    swp(x[i], y[i]);
    auto [x, y] = ops[i];
    tie(p[i], q[i]) = tie(pos[x], pos[y]);
    swp(p[i], q[i]);
  }
  return k;
}

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