Submission #233220

#	Time	Username	Problem	Language	Result	Execution time	Memory
233220		FieryPhoenix	Sorting (IOI15_sorting)	C++11	0 / 100	7 ms	1024 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];
queue<pair<int,int>>q;
int pos[200001];

void dfs(int node){
  vis[node]=true;
  if (!vis[to[node]]){
    dfs(to[node]);
    q.push({arr[node],arr[to[node]]});
  }
}

bool check(int mid){
  while (!q.empty())
    q.pop();
  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]]);
  for (int i=0;i<N;i++)
    to[i]=arr[i];
  int comps=0;
  for (int i=0;i<N;i++){
    pos[arr[i]]=i;
    if (!vis[i]){
      comps++;
      dfs(i);
    }
  }
  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];
    Y[i]=y[i];
  }
  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]=pos[q.front().first];
      Q[i]=pos[q.front().second];
      swap(pos[arr[X[i]]],pos[arr[Y[i]]]);
      swap(arr[X[i]],arr[Y[i]]);
      q.pop();
    }
  }
  for (int i=1;i<=high;i++){
    swap(S[X[i]],S[Y[i]]);
    swap(S[P[i]],S[Q[i]]);
  }
  for (int i=0;i<N;i++)
    if (S[i]!=i)
      assert(0);
  return high;
}

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