Submission #172469

#	Time	Username	Problem	Language	Result	Execution time	Memory
172469		AlexLuchianov	Sorting (IOI15_sorting)	C++14	100 / 100	908 ms	29800 KiB

sorting

#include "sorting.h"
#include <iostream>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 600000;
int xswap[1 + nmax], yswap[1 + nmax];
int init[1 + nmax];
int pswap[1 + nmax], qswap[1 + nmax];
int n;
int v[1 + nmax], f[1 + nmax], invf[1 + nmax], freq[1 + nmax];

int test(int moves){
  for(int i = 0; i < moves; i++)
    pswap[i] = qswap[i] = 0;
  for(int i = 0; i < n; i++)
    v[i] = init[i];
  for(int i = 0; i < n; i++) {
    f[i] = i;
    invf[i] = i;
    freq[v[i]] = i;
  }
  for(int i = moves - 1; 0 <= i; i--) {
    std::swap(f[xswap[i]], f[yswap[i]]);
    invf[f[xswap[i]]] = xswap[i];
    invf[f[yswap[i]]] = yswap[i];
  }
  int ptr = 0;

  for(int i = 0; i < moves; i++){
    std::swap(f[xswap[i]], f[yswap[i]]);

    invf[f[xswap[i]]] = xswap[i];
    invf[f[yswap[i]]] = yswap[i];

    std::swap(v[xswap[i]], v[yswap[i]] );
    freq[v[xswap[i]]] = xswap[i];
    freq[v[yswap[i]]] = yswap[i];

    if(ptr < n){
      while(ptr < n && v[invf[ptr]] == ptr)
        ptr++;
      if(ptr < n){
        pswap[i] = invf[ptr];
        qswap[i] = freq[ptr];
        std::swap(v[pswap[i]], v[qswap[i]] );
        freq[v[pswap[i]]] = pswap[i];
        freq[v[qswap[i]]] = qswap[i];
        ptr++;
      }
    }
  }
  while(ptr < n && v[invf[ptr]] == ptr)
    ptr++;
  return ptr == n;
}

int binarysearch(int from, int to){
  if(from < to){
    int mid = (from + to) / 2;
    if(test(mid))
      return binarysearch(from, mid);
    else
      return binarysearch(mid + 1, to);
  } else
    return from;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
  n = N;
  for(int i = 0; i < N; i++)
    init[i] = S[i];
  for(int i = 0; i < M; i++) {
    xswap[i] = X[i];
    yswap[i] = Y[i];
  }
  int pos = binarysearch(0, M);
  test(pos);
  for(int i = 0; i < pos; i++) {
    P[i] = pswap[i];
    Q[i] = qswap[i];
	}
	return pos;
}
/*
5
4 3 2 1 0
6
0 1
1 2
2 3
3 4
0 1
1 2
*/

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