Submission #134319

#	Time	Username	Problem	Language	Result	Execution time	Memory
134319		Runtime_error_	Sorting (IOI15_sorting)	C++14	74 / 100	108 ms	17912 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 2e3+9;
int pos[inf],from[inf],origin[inf],posfrom[inf];

int findSwapPairs(int n, int a[], int m, int x[], int y[], int p[], int q[]){

    bool tr = 1;
    for(int i=0;i<n;i++){
        pos[ a[i] ] = i;
        origin[i] = a[i];
        if(a[i] != i)
            tr = 0;
    }
    if(tr)
        return 0;

    for(int i=0;i<m;i++){
        int l = 0;
        for(int j=0;j<n;j++){
            from[j] = j;
            a[j] = origin[j];
            p[j] = q[j] = 0;
            pos[ a[j] ] = j;
            posfrom[ from[j] ] = j;
        }
         for(int j=i;j>=0;j--){
            swap(posfrom[ from[ x[j] ] ] , posfrom[ from[ y[j] ] ]);
            swap( from[ x[j] ] , from[ y[j] ] );
        }
        /*for(int j=0;j<n;j++)
            cout<<from[j]<<" ";
        cout<<endl;*/

        for(int j=0;j<=i;j++){

            swap(pos[ a[ x[j] ] ] , pos[ a[ y[j] ] ]);
            swap(posfrom[ from[ x[j] ] ] , posfrom[ from[ y[j] ] ]);

            swap(a[ x[j] ] , a[ y[j] ] );
            swap(from[ x[j] ] , from[ y[j] ]);

            int idx,idfrom;

            while(l<n){
                idx = pos[l];
                idfrom = posfrom[l];
                //for(idx = 0;idx<n && a[idx] != l;idx++);
                //for(idfrom = 0;idfrom<n && from[idfrom] != l;idfrom++);
                if(idx != idfrom)
                    break;
                l++;
            }
            swap(pos[ a[ idx ] ] , pos[ a[ idfrom ] ]);
            swap(a[idx],a[idfrom]);

            //cout<<l<<" "<<idx<<" "<<idfrom<<endl;
            p[j] = idx,q[j] = idfrom;
        }
        //for(int i=0;i<n;i++)
        //    cout<<a[i]<<" ";
        tr = 1;
        for(int i=0;i<n;i++)
            if(a[i] != i)
                tr = 0;
        if(tr)
            return i+1;
    }
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:64:17: warning: declaration of 'i' shadows a previous local [-Wshadow]
         for(int i=0;i<n;i++)
                 ^
sorting.cpp:19:13: note: shadowed declaration is here
     for(int i=0;i<m;i++){
             ^
sorting.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
sorting.cpp:55:51: warning: 'idfrom' may be used uninitialized in this function [-Wmaybe-uninitialized]
             swap(pos[ a[ idx ] ] , pos[ a[ idfrom ] ]);
                                                   ^
sorting.cpp:55:30: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
             swap(pos[ a[ idx ] ] , pos[ a[ idfrom ] ]);
                              ^

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