oj.uz

Submission #802465

# Submission time Handle Problem Language Result Execution time Memory
802465 2023-08-02T12:24:00 Z erray Sorting (IOI15_sorting) C++17
0 / 100
 1 ms 468 KB 
#include "sorting.h"\

#include<bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/codes/ioi15_d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

template<typename T> 
vector<T> inverse_fuck(T* a, int N) {
  vector<T> res(N);
  for (int i = 0; i < N; ++i) {
    res[i] = a[i];
  }
  return res;
}

int findSwapPairs(int N, int __S[], int M, int __X[], int __Y[], int __P[], int __Q[]) {
  auto S = inverse_fuck(__S, N);
  auto X = inverse_fuck(__X, M);
  auto Y = inverse_fuck(__Y, M);
  vector<int> P(M), Q(M);
  debug(X, Y);
  auto Check = [&](int m) {
    debug(m);
    auto a = S;
    for (int i = 0; i < m; ++i) {
      swap(a[X[i]], a[Y[i]]);
    }
    debug(a);
    vector<bool> vis(N);
    vector<array<int, 2>> swaps;
    for (int i = 0; i < N; ++i) {
      if (vis[i]) {
        continue;
      }
      int v = i;
      while (a[v] != i) {
        swaps.push_back({v, a[v]});
        v = a[v];
        vis[v] = true;
      }
    }
    debug(swaps);
    int moves = int(swaps.size()); 
    if (moves > m) {
      return false;
    }
    a = S;
    vector<int> inv(N);
    for (int i = 0; i < N; ++i) {
      inv[a[i]] = i;
    }
    for (int i = 0; i < moves; ++i) {
      swap(inv[a[X[i]]], inv[a[Y[i]]]);
      swap(a[X[i]], a[Y[i]]);
      P[i] = inv[swaps[i][0]];
      Q[i] = inv[swaps[i][1]];
    }   
    while (moves < m) {
      P[moves] = Q[moves] = 0;
      ++moves;
    }
    return true;
  };  
  int low = 0, high = M;
  while (low < high) {
    int mid = (low + high) >> 1;
    if (!Check(mid)) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  debug(low);
  int ans = !Check(low) ? -1 : low;
  if (ans != -1) {
    for (int i = 0; i < ans; ++i) {
      __P[i] = P[i];
      __Q[i] = Q[i];
    }
  }
  return ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 26.0

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