Submission #233219

#	Time	Username	Problem	Language	Result	Execution time	Memory
233219		FieryPhoenix	Sorting (IOI15_sorting)	C++11	Compilation error	0 ms	0 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[ansX[i]],S[ansY[i]]);
  }
  for (int i=0;i<N;i++)
    if (S[i]!=i)
      assert(0);
  return high;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:78:12: error: 'ansX' was not declared in this scope
     swap(S[ansX[i]],S[ansY[i]]);
            ^~~~
sorting.cpp:78:12: note: suggested alternative: 'abs'
     swap(S[ansX[i]],S[ansY[i]]);
            ^~~~
            abs
sorting.cpp:78:23: error: 'ansY' was not declared in this scope
     swap(S[ansX[i]],S[ansY[i]]);
                       ^~~~
sorting.cpp:78:23: note: suggested alternative: 'abs'
     swap(S[ansX[i]],S[ansY[i]]);
                       ^~~~
                       abs