Submission #257144

#	Time	Username	Problem	Language	Result	Execution time	Memory
257144		eohomegrownapps	Sorting (IOI15_sorting)	C++14	100 / 100	558 ms	83448 KiB

sorting

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

struct SwapList{
    vector<int> index;
    vector<int> arr;
    int n;
    SwapList(int _n){
        n=_n;
        index.resize(n);
        arr.resize(n);
    }

    void set(int ind, int val){
        arr[ind]=val;
        index[val]=ind;
    }

    int get(int ind){
        return arr[ind];
    }

    int indexOf(int ind){
        return index[ind];
    }

    void swapIndices(int a, int b){
        swap(arr[a],arr[b]);
        swap(index[arr[a]],index[arr[b]]);
    }

    void swapValues(int a, int b){
        swapIndices(indexOf(a), indexOf(b));
    }
};

int n;

int *x, *y, *s, *p, *q;

bool success(int m){
    SwapList *nums = new SwapList(n);
    SwapList *current = new SwapList(n);
    for (int i = 0; i<n; i++){
        nums->set(i,i);
        current->set(i,s[i]);
    }
    for (int i = m-1; i>=0; i--){
        nums->swapIndices(x[i],y[i]);
    }

    int curel = 0;

    for (int i = 0; i<m; i++){
        //perform opponent's swap
        current->swapIndices(x[i],y[i]);
        nums->swapIndices(x[i],y[i]);
        //which to move?
        while (curel<n&&current->indexOf(curel)==nums->indexOf(curel)){
            curel++;
        }
        if (curel==n){
            for (int j = i; j<m; j++){
                p[i]=0;
                q[i]=0;
            }
            return true;
        }
        //indices to swap:
        int curel_pos_current = current->indexOf(curel);
        int curel_pos_nums = nums->indexOf(curel);
        p[i]=curel_pos_current;
        q[i]=curel_pos_nums;
        current->swapIndices(curel_pos_current,curel_pos_nums);
        /*for (int i = 0; i<n; i++){
            cout<<current->get(i)<<' ';
        }cout<<'\n';*/
    }
    for (int i = 0; i<n; i++){
        if (current->get(i)!=i){return false;}
    }
    return true;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n=N;x=X;y=Y;s=S;p=P;q=Q;
    int l = 0, r = M;
    while (l<=r){
        int mid = (l+r)/2;
        bool s = success(mid);
        //cout<<mid<<' '<<s<<'\n';
        if (s){
            r=mid-1;
        } else {
            l=mid+1;
        }
    }
    //l is correct value
    success(l);
	return l;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:91:14: warning: declaration of 's' shadows a global declaration [-Wshadow]
         bool s = success(mid);
              ^
sorting.cpp:40:14: note: shadowed declaration is here
 int *x, *y, *s, *p, *q;
              ^

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