Submission #66313

#	Time	Username	Problem	Language	Result	Execution time	Memory
66313		Just_Solve_The_Problem	Sorting (IOI15_sorting)	C++11	100 / 100	730 ms	20216 KiB

sorting

#include <bits/stdc++.h>
//#include "sorting.h"
//#include "grader.cpp"

using namespace std;

const int nn = (int)1e6 + 7;

int x[nn], y[nn], p[nn], q[nn], n, s[nn], m;
int pos[nn], pos1[nn], p1[nn], p2[nn];

void upd(int a, int b) {
  swap(p1[a], p1[b]);
  p2[p1[a]] = a;
  p2[p1[b]] = b;
}

void upd1(int a, int b) {
  swap(pos[a], pos[b]);
  pos1[pos[a]] = a;
  pos1[pos[b]] = b;
}

bool check(int val) {
  iota(pos, pos + n, 0);
  iota(p1, p1 + n, 0);
  for (int i = 0; i < val; i++) {
    swap(pos[x[i]], pos[y[i]]);
  }
  for (int i = 0; i < n; i++) {
    p2[p1[i]] = i;
    pos1[pos[i]] = i;
  }
  int cur = 0, ppos;
  for (int i = val - 1; i >= 0; i--) {
    if (cur < n)
      ppos = pos1[cur];
    if (cur < n && s[cur] == p1[ppos]) {
      i++;
      cur++;
      continue;
    }
    if (cur < n && s[cur] != p1[ppos]) {
      upd(p2[s[cur]], ppos);
    }
    cur++;
    upd(x[i], y[i]);
    upd1(x[i], y[i]);
  }
  for (int i = 0; i < n; i++) {
    if (s[i] != p1[i]) return 0;
  }
  return 1;
}

int asd;

void make(int val) {
  iota(pos, pos + n, 0);
  iota(p1, p1 + n, 0);
  for (int i = 0; i < val; i++) {
    swap(pos[x[i]], pos[y[i]]);
  }
  for (int i = 0; i < n; i++) {
    p2[p1[i]] = i;
    pos1[pos[i]] = i;
  }
  bool fl = 0;
  int cur = 0, ppos;
  asd = val - 1;
  for (int i = val - 1; i >= 0; i--) {
    if (cur < n)
      ppos = pos1[cur];
    if (cur < n && s[cur] == p1[ppos]) {
      i++;
      cur++;
      continue;
    }
    if (cur < n && s[cur] != p1[ppos]) {
      p[asd] = p2[s[cur]];
      q[asd--] = ppos;
      upd(p2[s[cur]], ppos);
    }
    cur++;
    upd(x[i], y[i]);
    upd1(x[i], y[i]);
  }
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
  n = N; m = M;
  for (int i = 0; i < n; i++)
    s[i] = S[i];
  for (int i = 0; i < m; i++) {
    x[i] = X[i]; y[i] = Y[i];
  }
  int l = 0;
  int r = m;
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
      r = mid;
    } else {
      l = mid;
    }
  }
  if (check(l)) r = l;
  make(r);
  for (int i = 0; i <= asd; i++) {
    P[i] = 0;
    Q[i] = 0;
  }
  for (int i = asd + 1; i < r; i++) {
    P[i] = p[i];
    Q[i] = q[i];
  }
  return r;
}

//main() {
//  int n;
//  cin >> n;
//  int S[n];
//  for (int i = 0; i < n; i++) {
//    cin >> S[i];
//  }
//  int m;
//  cin >> m;
//  int X[M], Y[M];
//  for (int i = 0; i < m; i++) {
//    cin >> X[i] >> Y[i];
//  }
//  int ans1[M], ans2[M];
//  int sz = findSwapPairs(n, S, m, X, Y, ans1, ans2);
//  cout << sz << endl;
//  for (int i = 0; i < sz; i++) {
//    cout << ans1[i] << ' ' << ans2[i] << endl;
//  }
//}

Compilation message (stderr)

sorting.cpp: In function 'void make(int)':
sorting.cpp:68:8: warning: unused variable 'fl' [-Wunused-variable]
   bool fl = 0;
        ^~

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