Submission #1326113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326113		SmuggingSpun	Sorting (IOI15_sorting)	C++20	74 / 100	87 ms	14272 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));
    vector<int>pos(n);
    for(int i = 0; i < m; i++){
      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;
  }
}
namespace sub5{
  int solve(int p[], int q[]){
    vector<int>pos(n);
    int low = 0, high = m, ans;
    while(low <= high){
      int mid = (low + high) >> 1;
      vector<int>S(s, s + n);
      iota(pos.begin(), pos.end(), 0);
      for(int i = 0; i < mid; i++){
        iota(pos.begin(), pos.end(), 0);
        for(int j = i + 1; j < mid; 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[pos[j]], S[find(S.begin(), S.end(), j) - S.begin()]);
            break;
          }
        }
      }
      bool flag = true;
      for(int i = 0; i < n; i++){
        if(S[i] != i){
          flag = false;
          break;
        }
      }
      if(flag){
        high = (ans = mid) - 1;
      }
      else{
        low = mid + 1;
      }
    }
    memset(p, 0, sizeof(p));
    memset(q, 0, sizeof(q));
    for(int i = 0; i < ans; i++){
      iota(pos.begin(), pos.end(), 0);
      for(int j = i + 1; j < ans; 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 ans;
  }
}
namespace sub6{
  int solve(int p[], int q[]){
    vector<int>pos(n), ps(n);
    int low = 0, high = m, ans;
    while(low <= high){
      int mid = (low + high) >> 1, cnt = 0;
      vector<int>S(s, s + n);
      for(int i = 0; i < mid; i++){
        swap(S[x[i]], S[y[i]]);
      }
      for(int i = 0; i < n; i++){
        ps[S[i]] = i;
      }
      for(int i = 0; i < n; i++){
        if(ps[i] != i){
          cnt++;
          swap(S[i], S[ps[i]]);
          swap(ps[S[i]], ps[S[ps[i]]]);
        }
      }
      if(cnt <= mid){
        high = (ans = mid) - 1;
      }
      else{
        low = mid + 1;
      }
    }
    memset(p, 0, sizeof(p));
    memset(q, 0, sizeof(q));
    vector<int>S(s, s + n);
    for(int i = 0; i < ans; i++){
      swap(S[x[i]], S[y[i]]);
    }
    for(int i = 0; i < n; i++){
      ps[S[i]] = i;
    }
    for(int i = 0; i < n; i++){
      ps[s[i]] = i;
    }
    for(int i = 0, j = 0; i < n; i++){
      if(S[i] != i){
        swap(p[j] = S[i], q[j] = S[ps[i]]);
        swap(ps[S[i]], ps[S[ps[i]]]);
        j++;
      }
    }
    for(int i = 0; i < ans; i++){
      swap(s[x[i]], s[y[i]]);
      swap(ps[s[x[i]]], ps[s[y[i]]]);
      int x = p[i], y = q[i];
      swap(s[p[i] = ps[x]], s[q[i] = ps[y]]);
      swap(ps[x], ps[y]);
    }
    return ans;
  }
}
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);
  }
  if(n <= 2000){
    return sub5::solve(P, Q);
  }
  return sub6::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 sub5::solve(int*, int*)':
sorting.cpp:105:25: warning: 'sizeof' on array function parameter 'p' will return size of 'int*' [-Wsizeof-array-argument]
  105 |     memset(p, 0, sizeof(p));
      |                        ~^~
sorting.cpp:71:17: note: declared here
   71 |   int solve(int p[], int q[]){
      |             ~~~~^~~
sorting.cpp:106:25: warning: 'sizeof' on array function parameter 'q' will return size of 'int*' [-Wsizeof-array-argument]
  106 |     memset(q, 0, sizeof(q));
      |                        ~^~
sorting.cpp:71:26: note: declared here
   71 |   int solve(int p[], int q[]){
      |                      ~~~~^~~
sorting.cpp: In function 'int sub6::solve(int*, int*)':
sorting.cpp:150:25: warning: 'sizeof' on array function parameter 'p' will return size of 'int*' [-Wsizeof-array-argument]
  150 |     memset(p, 0, sizeof(p));
      |                        ~^~
sorting.cpp:124:17: note: declared here
  124 |   int solve(int p[], int q[]){
      |             ~~~~^~~
sorting.cpp:151:25: warning: 'sizeof' on array function parameter 'q' will return size of 'int*' [-Wsizeof-array-argument]
  151 |     memset(q, 0, sizeof(q));
      |                        ~^~
sorting.cpp:124:26: note: declared here
  124 |   int solve(int p[], int q[]){
      |                      ~~~~^~~

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