Submission #114137

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
114137	2019-05-30T14:05:21 Z	nvmdava	Sorting (IOI15_sorting)	C++17	Compilation error	0 ms	0 KB

sorting

//#include "sorting.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;

#define NN 200005

int val[NN];
int loc[NN];
int n;
vector<pii> sw;

bool in[NN];

void dfs(int s, int now){
    in[now] = 1;
    if(now == s) return;
    dfs(s, S[now]);
}

int findSwapPairs(int N, int qq[], int M, int X[], int Y[], int P[], int Q[]) {
    int cyc, l = 0, r = N, m, i;

    for(i = 0; i < N; i++){
        val[i] = qq[i];
        loc[val[i]] = i;
    }

    while(l != r){
        cyc = 0;
        m = (l + r) >> 1;
        for(i = 0; i < m; i++)
            swap(val[X[i]], val[Y[i]]);

        for(i = 0; i < N; i++){
            if(in[i]) continue;
            cyc++;
            dfs(i, val[i]);
        }
        if(N - cyc <= m) r = m;
        else l = m + 1;
        memset(in, 0, sizeof in);
        for(i = 0; i < N; i++)
            val[loc[i]] = i;

    }

    for(i = 0; i < r; i++)
        swap(S[X[i]], S[Y[i]]);
    for(i = 0; i < N; i++){
        while(S[i] != i){
            sw.push_back({S[i], i});
            swap(S[i], S[S[i]]);
        }
    }

    for(i = 0; i < r; i++){
        swap(val[X[i]], val[Y[i]]);
        swap(loc[val[X[i]]], loc[val[Y[i]]]);
        if(sw.empty()){
            P[i] = 0;
            Q[i] = 0;
        } else {
            P[i] = loc[sw.back().ff];
            Q[i] = loc[sw.back().ss];
            swap(val[P[i]], val[Q[i]]);
            swap(loc[val[P[i]]], loc[val[Q[i]]]);
            sw.pop_back();
        }
    }

    return l;
}

Compilation message

sorting.cpp: In function 'void dfs(int, int)':
sorting.cpp:20:12: error: 'S' was not declared in this scope
     dfs(s, S[now]);
            ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:51:14: error: 'S' was not declared in this scope
         swap(S[X[i]], S[Y[i]]);
              ^
sorting.cpp:53:15: error: 'S' was not declared in this scope
         while(S[i] != i){
               ^
sorting.cpp:54:35: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(<brace-enclosed initializer list>)'
             sw.push_back({S[i], i});
                                   ^
In file included from /usr/include/c++/7/vector:64:0,
                 from /usr/include/c++/7/functional:61,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:71,
                 from sorting.cpp:2:
/usr/include/c++/7/bits/stl_vector.h:939:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]
       push_back(const value_type& __x)
       ^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:939:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type& {aka const std::pair<int, int>&}'
/usr/include/c++/7/bits/stl_vector.h:953:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]
       push_back(value_type&& __x)
       ^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:953:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::pair<int, int> >::value_type&& {aka std::pair<int, int>&&}'
sorting.cpp:23:40: warning: unused parameter 'M' [-Wunused-parameter]
 int findSwapPairs(int N, int qq[], int M, int X[], int Y[], int P[], int Q[]) {
                                        ^