Submission #1247821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247821		_is_this_fft_	Sorting (IOI15_sorting)	C++20	16 / 100	11 ms	13132 KiB

sorting

#include "sorting.h"
#include <vector>
#include <numeric>

using namespace std;

int findSwapPairs (int n, int init [], int m, int X[], int Y[], int P[], int Q[]) {
  // assume it always ends after exactly n turns
  vector<vector<int>> perms (n);

  // position perms[i][j] will end up at position j if we don't touch it
  perms[n - 1] = vector<int> (n);
  iota(perms[n - 1].begin(), perms[n - 1].end(), 0);

  for (int i = n - 2; i >= 0; i--) {
    perms[i] = perms[i + 1];
    swap(perms[i][X[i + 1]], perms[i][Y[i + 1]]);
  }

  vector<int> cur (init, init + n);

  for (int i = 0; i < n; i++) {
    swap(cur[X[i]], cur[Y[i]]);

    // find a thing that's out of place
    int k = -1;
    for (int j = 0; j < n; j++) {
      if (cur[perms[i][j]] != j) {
        k = j;
        break;
      }
    }

    if (k == -1) {
      P[i] = 0;
      Q[i] = 0;
      continue;
    }

    // the value k must be moved to position perms[i][k]
    int pk = -1;
    for (int j = 0; j < n; j++) {
      if (cur[j] == k) {
        pk = j;
      }
    }

    P[i] = pk;
    Q[i] = perms[i][k];
    swap(cur[P[i]], cur[Q[i]]);
  }

  return n;
}

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