Submission #1122300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122300		epicci23	Sorting (IOI15_sorting)	C++17	100 / 100	247 ms	31064 KiB

sorting

#include "bits/stdc++.h"
#include "sorting.h"
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
  int n,q;
  n = N , q = M;
  int ar[n+5];
  for(int i=1;i<=n;i++) ar[i] = S[i-1]+1;
  array<int,2> v[q+5];
  for(int i=1;i<=q;i++) v[i][0] = X[i-1]+1 , v[i][1] = Y[i-1]+1;
  
  int l=0,r=q;
  vector<array<int,2>> ans;

  while(l<r){
    int m=(l+r)/2;
    int ta[n+5],tb[n+5],a[n+5],b[n+5];
    vector<array<int,2>> lol;
    for(int i=1;i<=n;i++) ta[i]=tb[i]=i;
    for(int i=1;i<=n;i++) a[i]=ar[i];
    for(int i=1;i<=n;i++) b[ar[i]]=i;

    for(int i=m;i>=1;i--){
      int s1 = v[i][0] , s2 = v[i][1];
      int v1 = ta[s1] , v2 = ta[s2];
      swap(ta[s1],ta[s2]);
      tb[v1] = s2;
      tb[v2] = s1;
    }
   
    int p = n;

    for(int i=1;i<=m;i++){
      int s1 = v[i][0] , s2 = v[i][1];
      int v1 = ta[s1] , v2 = ta[s2];
      swap(ta[s1],ta[s2]);
      tb[v1] = s2;
      tb[v2] = s1;

      v1 = a[s1] , v2 = a[s2];
      swap(a[s1],a[s2]);
      b[v1] = s2;
      b[v2] = s1;

      while(p>=1 && b[p] == tb[p]) p--;

      if(p==0) lol.push_back({1,1});
      else{
      	lol.push_back({b[p],tb[p]});

      	s1 = b[p] , s2 = tb[p];
        v1 = a[s1] , v2 = a[s2];
        swap(a[s1],a[s2]);
        b[v1] = s2;
        b[v2] = s1;

        p--;
      }
    }

    while(p>=1 && b[p] == tb[p]) p--;

    if(p==0){
      r = m;
      ans = lol;
    }
    else l = m + 1;
  }
   
  for(int i = 0 ; i < l ; i++){
  	P[i] = ans[i][0] - 1;
  	Q[i] = ans[i][1] - 1;
  }

  return l;
}

/*void _(){
  int n,q;
  cin >> n >> q;
  int ar[n+5];
  for(int i=1;i<=n;i++) cin >> ar[i];
  array<int,2> v[q+5];
  for(int i=1;i<=q;i++) cin >> v[i][0] >> v[i][1];
  
  int l=0,r=q;
  vector<array<int,2>> ans;

  while(l<r){
    int m=(l+r)/2;
    int ta[n+5],tb[n+5],a[n+5],b[n+5];
    vector<array<int,2>> lol;
    for(int i=1;i<=n;i++) ta[i]=tb[i]=i;
    for(int i=1;i<=n;i++) a[i]=ar[i];
    for(int i=1;i<=n;i++) b[ar[i]]=i;

    for(int i=m;i>=1;i--){
      int s1 = v[i][0] , s2 = v[i][1];
      int v1 = ta[s1] , v2 = ta[s2];
      swap(ta[s1],ta[s2]);
      tb[v1] = s2;
      tb[v2] = s1;
    }
   
    int p = n;

    for(int i=1;i<=m;i++){
      int s1 = v[i][0] , s2 = v[i][1];
      int v1 = ta[s1] , v2 = ta[s2];
      swap(ta[s1],ta[s2]);
      tb[v1] = s2;
      tb[v2] = s1;

      v1 = a[s1] , v2 = a[s2];
      swap(a[s1],a[s2]);
      b[v1] = s2;
      b[v2] = s1;

      while(p>=1 && b[p] == tb[p]) p--;

      if(p==0) lol.push_back({1,1});
      else{
      	lol.push_back({b[p],tb[p]});

      	s1 = b[p] , s2 = tb[p];
        v1 = a[s1] , v2 = a[s2];
        swap(a[s1],a[s2]);
        b[v1] = s2;
        b[v2] = s1;

        p--;
      }
    }

    while(p>=1 && b[p] == tb[p]) p--;

    if(p==0){
      r = m;
      ans = lol;
    }
    else l = m + 1;
  }
  
  cout << l << '\n';
  for(auto x:ans) cout << x[0] << ' ' << x[1] << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

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