Submission #1185371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185371		Kerim	Sorting (IOI15_sorting)	C++20	0 / 100	1 ms	328 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;
    }
  }
  return k;
}

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