Submission #233228

#	Time	Username	Problem	Language	Result	Execution time	Memory
233228		FieryPhoenix	Sorting (IOI15_sorting)	C++11	100 / 100	242 ms	34048 KiB

sorting

#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

int N,S[200001];
int M,X[600001],Y[600001];
int arr[200001];
bool vis[200001];
int to[200001];
deque<pair<int,int>>q;
int pos[200001];

void dfs(int node){
  vis[node]=true;
  if (!vis[arr[node]]){
    q.push_back({node,arr[node]});
    dfs(arr[node]);
    //cout<<"Q: "<<arr[node]<<' '<<arr[to[node]]<<endl;
  }
}

bool check(int mid){
  q.clear();
  for (int i=0;i<N;i++){
    arr[i]=S[i];
    vis[i]=false;
  }
  for (int i=1;i<=mid;i++)
    swap(arr[X[i]],arr[Y[i]]);
 int comps=0;
  for (int i=0;i<N;i++){
    pos[arr[i]]=i;
    if (!vis[arr[i]]){
      comps++;
      q.push_back({i,arr[i]});
      dfs(arr[i]);
      q.pop_back();
    }
  }
  return N-comps<=mid;
}
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++)
    S[i]=s[i];
  M=m;
  for (int i=1;i<=M;i++){
    X[i]=x[i-1];
    Y[i]=y[i-1];
  }
  int low=-1,high=M+1;
  while (low+1<high){
    int mid=(low+high)/2;
    if (check(mid))
      high=mid;
    else
      low=mid;
  }
  check(high);
  for (int i=high;i>=1;i--){
    if (!q.empty()){
      P[i-1]=pos[q[0].first];
      Q[i-1]=pos[q[0].second];
      swap(pos[arr[X[i]]],pos[arr[Y[i]]]);
      swap(arr[X[i]],arr[Y[i]]);
      q.pop_front();
    }
  }
  for (int i=1;i<=high;i++){
    swap(S[X[i]],S[Y[i]]);
    swap(S[P[i-1]],S[Q[i-1]]);
  }
  for (int i=0;i<N;i++)
    if (S[i]!=i)
      assert(0);
  return high;
}

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