oj.uz

Submission #172467

# Submission time Handle Problem Language Result Execution time Memory
172467 2020-01-01T15:25:25 Z AlexLuchianov Sorting (IOI15_sorting) C++14
0 / 100
 4 ms 764 KB 
#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 = 200000;
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++;
      }
    }
  }
  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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 764 KB Output isn't correct
2 Halted 0 ms 0 KB -