oj.uz

Submission #172468

# Submission time Handle Problem Language Result Execution time Memory
172468 2020-01-01T15:27:17 Z AlexLuchianov Sorting (IOI15_sorting) C++14
74 / 100
 53 ms 22520 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++;
      }
    }
  }
  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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 504 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 3 ms 504 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 380 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 4 ms 760 KB Output is correct
22 Correct 3 ms 732 KB Output is correct
23 Correct 4 ms 760 KB Output is correct
24 Correct 3 ms 760 KB Output is correct
25 Correct 3 ms 760 KB Output is correct
26 Correct 3 ms 760 KB Output is correct
27 Correct 3 ms 764 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 4 ms 612 KB Output is correct
10 Correct 4 ms 636 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 4 ms 760 KB Output is correct
13 Correct 4 ms 632 KB Output is correct
14 Correct 3 ms 632 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 4 ms 612 KB Output is correct
10 Correct 4 ms 636 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 4 ms 760 KB Output is correct
13 Correct 4 ms 632 KB Output is correct
14 Correct 3 ms 632 KB Output is correct
15 Runtime error 53 ms 22520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -