Submission #245286

#	Time	Username	Problem	Language	Result	Execution time	Memory
245286		ant101	Sorting (IOI15_sorting)	C++14	Compilation error	0 ms	0 KiB

sorting

#include "sorting.h"
#include <algorithm>

using namespace std;

const int MAXN = 200005;

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    int lo=0, hi=m;

    while(lo<hi){
        int mid=lo+(hi-lo)/2;
        vector<int> fp(n), fpidx(n), sc(s, s+n);
        for(int i=0;i<n;++i) fp[i]=i;

        for(int i=0;i<mid;++i){
            swap(fp[x[i]], fp[y[i]]);
        }
        for(int i=0;i<n;++i){
            fpidx[fp[i]]=i;
        }

        vector<int> perm(n), idx(n);
        for(int i=0;i<n;++i){
            perm[i]=i;
            idx[perm[i]]=i;
        }
        int j=0;
        for(int i=0;i<mid;++i){
            swap(sc[x[i]], sc[y[i]]);
            swap(perm[x[i]], perm[y[i]]);
            swap(idx[perm[x[i]]], idx[perm[y[i]]]);

            bool found=false;
            for(;j<n;j++){
                int jj=idx[j];
                if(fpidx[perm[jj]]!=sc[jj]){
                    found=true;
                    p[i]=jj;
                    q[i]=idx[fp[sc[jj]]];
                    swap(sc[p[i]], sc[q[i]]);
                    break;
                }
            }
            if(!found) p[i]=q[i]=0;
        }
        bool ok=true;
        for(int i=0;i<n;++i) if(sc[i]!=i) ok=false;
        if(ok){
            hi=mid;
        }else{
            lo=mid+1;
        }

    }
    vector<int> fp(n), fpidx(n), sc(s, s+n);
    for(int i=0;i<n;++i) fp[i]=i;

    for(int i=0;i<lo;++i){
        swap(fp[x[i]], fp[y[i]]);
    }
    for(int i=0;i<n;++i){
        fpidx[fp[i]]=i;
    }

    vector<int> perm(n), idx(n);
    for(int i=0;i<n;++i){
        perm[i]=i;
        idx[perm[i]]=i;
    }
    int j=0;
    for(int i=0;i<lo;++i){
        swap(sc[x[i]], sc[y[i]]);
        swap(perm[x[i]], perm[y[i]]);
        swap(idx[perm[x[i]]], idx[perm[y[i]]]);
        for(;j<n;j++){
            int jj=idx[j];
            if(fpidx[perm[jj]]!=sc[jj]){
                p[i]=jj;
                q[i]=idx[fp[sc[jj]]];
                swap(sc[p[i]], sc[q[i]]);
                break;
            }
        }
    }
    return lo;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:14:9: error: 'vector' was not declared in this scope
         vector<int> fp(n), fpidx(n), sc(s, s+n);
         ^~~~~~
sorting.cpp:14:9: note: suggested alternative: 'qecvt_r'
         vector<int> fp(n), fpidx(n), sc(s, s+n);
         ^~~~~~
         qecvt_r
sorting.cpp:14:16: error: expected primary-expression before 'int'
         vector<int> fp(n), fpidx(n), sc(s, s+n);
                ^~~
sorting.cpp:15:30: error: 'fp' was not declared in this scope
         for(int i=0;i<n;++i) fp[i]=i;
                              ^~
sorting.cpp:15:30: note: suggested alternative: 'p'
         for(int i=0;i<n;++i) fp[i]=i;
                              ^~
                              p
sorting.cpp:18:18: error: 'fp' was not declared in this scope
             swap(fp[x[i]], fp[y[i]]);
                  ^~
sorting.cpp:18:18: note: suggested alternative: 'p'
             swap(fp[x[i]], fp[y[i]]);
                  ^~
                  p
sorting.cpp:21:13: error: 'fpidx' was not declared in this scope
             fpidx[fp[i]]=i;
             ^~~~~
sorting.cpp:21:19: error: 'fp' was not declared in this scope
             fpidx[fp[i]]=i;
                   ^~
sorting.cpp:21:19: note: suggested alternative: 'p'
             fpidx[fp[i]]=i;
                   ^~
                   p
sorting.cpp:24:16: error: expected primary-expression before 'int'
         vector<int> perm(n), idx(n);
                ^~~
sorting.cpp:26:13: error: 'perm' was not declared in this scope
             perm[i]=i;
             ^~~~
sorting.cpp:27:13: error: 'idx' was not declared in this scope
             idx[perm[i]]=i;
             ^~~
sorting.cpp:31:18: error: 'sc' was not declared in this scope
             swap(sc[x[i]], sc[y[i]]);
                  ^~
sorting.cpp:31:18: note: suggested alternative: 's'
             swap(sc[x[i]], sc[y[i]]);
                  ^~
                  s
sorting.cpp:32:18: error: 'perm' was not declared in this scope
             swap(perm[x[i]], perm[y[i]]);
                  ^~~~
sorting.cpp:33:18: error: 'idx' was not declared in this scope
             swap(idx[perm[x[i]]], idx[perm[y[i]]]);
                  ^~~
sorting.cpp:38:20: error: 'fpidx' was not declared in this scope
                 if(fpidx[perm[jj]]!=sc[jj]){
                    ^~~~~
sorting.cpp:41:30: error: 'fp' was not declared in this scope
                     q[i]=idx[fp[sc[jj]]];
                              ^~
sorting.cpp:41:30: note: suggested alternative: 'p'
                     q[i]=idx[fp[sc[jj]]];
                              ^~
                              p
sorting.cpp:49:33: error: 'sc' was not declared in this scope
         for(int i=0;i<n;++i) if(sc[i]!=i) ok=false;
                                 ^~
sorting.cpp:49:33: note: suggested alternative: 's'
         for(int i=0;i<n;++i) if(sc[i]!=i) ok=false;
                                 ^~
                                 s
sorting.cpp:57:5: error: 'vector' was not declared in this scope
     vector<int> fp(n), fpidx(n), sc(s, s+n);
     ^~~~~~
sorting.cpp:57:5: note: suggested alternative: 'qecvt_r'
     vector<int> fp(n), fpidx(n), sc(s, s+n);
     ^~~~~~
     qecvt_r
sorting.cpp:57:12: error: expected primary-expression before 'int'
     vector<int> fp(n), fpidx(n), sc(s, s+n);
            ^~~
sorting.cpp:58:26: error: 'fp' was not declared in this scope
     for(int i=0;i<n;++i) fp[i]=i;
                          ^~
sorting.cpp:58:26: note: suggested alternative: 'p'
     for(int i=0;i<n;++i) fp[i]=i;
                          ^~
                          p
sorting.cpp:61:14: error: 'fp' was not declared in this scope
         swap(fp[x[i]], fp[y[i]]);
              ^~
sorting.cpp:61:14: note: suggested alternative: 'p'
         swap(fp[x[i]], fp[y[i]]);
              ^~
              p
sorting.cpp:64:9: error: 'fpidx' was not declared in this scope
         fpidx[fp[i]]=i;
         ^~~~~
sorting.cpp:64:15: error: 'fp' was not declared in this scope
         fpidx[fp[i]]=i;
               ^~
sorting.cpp:64:15: note: suggested alternative: 'p'
         fpidx[fp[i]]=i;
               ^~
               p
sorting.cpp:67:12: error: expected primary-expression before 'int'
     vector<int> perm(n), idx(n);
            ^~~
sorting.cpp:69:9: error: 'perm' was not declared in this scope
         perm[i]=i;
         ^~~~
sorting.cpp:70:9: error: 'idx' was not declared in this scope
         idx[perm[i]]=i;
         ^~~
sorting.cpp:70:9: note: suggested alternative: 'id_t'
         idx[perm[i]]=i;
         ^~~
         id_t
sorting.cpp:74:14: error: 'sc' was not declared in this scope
         swap(sc[x[i]], sc[y[i]]);
              ^~
sorting.cpp:74:14: note: suggested alternative: 's'
         swap(sc[x[i]], sc[y[i]]);
              ^~
              s
sorting.cpp:75:14: error: 'perm' was not declared in this scope
         swap(perm[x[i]], perm[y[i]]);
              ^~~~
sorting.cpp:76:14: error: 'idx' was not declared in this scope
         swap(idx[perm[x[i]]], idx[perm[y[i]]]);
              ^~~
sorting.cpp:76:14: note: suggested alternative: 'id_t'
         swap(idx[perm[x[i]]], idx[perm[y[i]]]);
              ^~~
              id_t
sorting.cpp:79:16: error: 'fpidx' was not declared in this scope
             if(fpidx[perm[jj]]!=sc[jj]){
                ^~~~~
sorting.cpp:81:26: error: 'fp' was not declared in this scope
                 q[i]=idx[fp[sc[jj]]];
                          ^~
sorting.cpp:81:26: note: suggested alternative: 'p'
                 q[i]=idx[fp[sc[jj]]];
                          ^~
                          p
sorting.cpp:9:32: warning: unused parameter 's' [-Wunused-parameter]
 int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
                                ^