Submission #1326064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326064		SmuggingSpun	Sorting (IOI15_sorting)	C++20	54 / 100	85 ms	668 KiB

sorting

#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 2e5 + 5;
int n, m, s[lim], x[lim * 3], y[lim * 3];
bool check_sorted(){
  for(int i = 0; i < n; i++){
    if(s[i] != i){
      return false;
    }
  }
  return true;
}
namespace sub12{
  int solve(int p[], int q[]){
    int ans = 0;
    for(int i = 0; i < n; i++){
      if(s[i] != i){
        swap(s[p[ans] = i], s[q[ans] = s[i]]);
        ans++;
        i--;
      }
    }
    return ans;
  }
}
namespace sub3{
  int solve(int p[], int q[]){
    int ans = 0;
    for(int x = 2; x < n; x++){
      int i = find(s, s + n, x) - s;
      swap(s[0], s[1]);
      if(i == 0){
        i = 1;
      }
      else if(i == 1){
        i = 0;
      }
      swap(s[p[ans] = i], s[q[ans] = x]);
      ans++;
    }
    if(s[0] > s[1]){
      p[ans] = q[ans] = 0;
      ans++;
    }
    return ans;
  }
}
namespace sub4{
  int solve(int p[], int q[]){
    memset(p, 0, sizeof(p));
    memset(q, 0, sizeof(q));
    for(int i = 0; i < m; i++){
      vector<int>pos(n);
      iota(pos.begin(), pos.end(), 0);
      for(int j = i + 1; j < m; j++){
        swap(pos[x[j]], pos[y[j]]);
      }
      swap(s[x[i]], s[y[i]]);
      for(int j = 0; j < n; j++){
        if(s[pos[j]] != j){
          swap(s[p[i] = pos[j]], s[q[i] = find(s, s + n, j) - s]);
          break;
        }
      }
    }
    return m;
  }
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
  memcpy(s, S, sizeof(int) * (n = N));
  memcpy(x, X, sizeof(int) * (m = M));
  memcpy(y, Y, sizeof(int) * m);
  if(n == 1){
    return 0;
  }
  if(m == 30 * n){
    int mx = *max_element(x, x + m), my = *max_element(y, y + m);
    if(mx == 0){
      if(my == 0){
        return sub12::solve(P, Q);
      }
      if(my == 1){
        return sub3::solve(P, Q);
      }
    }
    return sub4::solve(P, Q);
  }
}

Compilation message (stderr)

sorting.cpp: In function 'int sub4::solve(int*, int*)':
sorting.cpp:51:25: warning: 'sizeof' on array function parameter 'p' will return size of 'int*' [-Wsizeof-array-argument]
   51 |     memset(p, 0, sizeof(p));
      |                        ~^~
sorting.cpp:50:17: note: declared here
   50 |   int solve(int p[], int q[]){
      |             ~~~~^~~
sorting.cpp:52:25: warning: 'sizeof' on array function parameter 'q' will return size of 'int*' [-Wsizeof-array-argument]
   52 |     memset(q, 0, sizeof(q));
      |                        ~^~
sorting.cpp:50:26: note: declared here
   50 |   int solve(int p[], int q[]){
      |                      ~~~~^~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:89:1: warning: control reaches end of non-void function [-Wreturn-type]
   89 | }
      | ^

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