Submission #484616

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
484616	2021-11-04T19:42:15 Z	couplefire	Sorting (IOI15_sorting)	C++17	Compilation error	0 ms	0 KB

sorting

void findSwapPairs(int n, vector<int> arr, int m, vector<int> x_moves, vector<int> y_moves, vector<int>& x_ans, vector<int>& y_ans){
    vector<int> fin_arr, x_todo, y_todo;
    auto calc = [&](int mid)->int{
        x_todo.clear(); y_todo.clear(); fin_arr = arr;
        for(int i = 0; i<mid; ++i)
            swap(fin_arr[x_moves[i]], fin_arr[y_moves[i]]);
        for(int i = 0; i<n; ++i)
            while(fin_arr[i]!=i)
                x_todo.push_back(fin_arr[i]), y_todo.push_back(fin_arr[fin_arr[i]]), 
                swap(fin_arr[i], fin_arr[fin_arr[i]]);
        return x_todo.size();
    };
    int lo = 0, hi = m;
    while(lo<hi){
        int mid = lo+(hi-lo)/2;
        if(calc(mid)<=mid) hi = mid;
        else lo = mid+1;
    } calc(lo);
    x_ans.resize(lo), y_ans.resize(lo);
    vector<int> pos(n);
    for(int i = 0; i<n; ++i)
        pos[arr[i]] = i;
    for(int i = 0; i<lo; ++i)
        swap(pos[arr[x_moves[i]]], pos[arr[y_moves[i]]]), swap(arr[x_moves[i]], arr[y_moves[i]]),
        x_ans[i] = pos[x_todo[i]], y_ans[i] = pos[y_todo[i]],
        swap(pos[arr[x_ans[i]]], pos[arr[y_ans[i]]]), swap(arr[x_ans[i]], arr[y_ans[i]]);
}

Compilation message

sorting.cpp:1:27: error: 'vector' has not been declared
    1 | void findSwapPairs(int n, vector<int> arr, int m, vector<int> x_moves, vector<int> y_moves, vector<int>& x_ans, vector<int>& y_ans){
      |                           ^~~~~~
sorting.cpp:1:33: error: expected ',' or '...' before '<' token
    1 | void findSwapPairs(int n, vector<int> arr, int m, vector<int> x_moves, vector<int> y_moves, vector<int>& x_ans, vector<int>& y_ans){
      |                                 ^
sorting.cpp: In function 'void findSwapPairs(int, int)':
sorting.cpp:2:5: error: 'vector' was not declared in this scope
    2 |     vector<int> fin_arr, x_todo, y_todo;
      |     ^~~~~~
sorting.cpp:2:12: error: expected primary-expression before 'int'
    2 |     vector<int> fin_arr, x_todo, y_todo;
      |            ^~~
sorting.cpp: In lambda function:
sorting.cpp:4:9: error: 'x_todo' was not declared in this scope
    4 |         x_todo.clear(); y_todo.clear(); fin_arr = arr;
      |         ^~~~~~
sorting.cpp:4:25: error: 'y_todo' was not declared in this scope
    4 |         x_todo.clear(); y_todo.clear(); fin_arr = arr;
      |                         ^~~~~~
sorting.cpp:4:41: error: 'fin_arr' was not declared in this scope
    4 |         x_todo.clear(); y_todo.clear(); fin_arr = arr;
      |                                         ^~~~~~~
sorting.cpp:4:51: error: 'arr' was not declared in this scope
    4 |         x_todo.clear(); y_todo.clear(); fin_arr = arr;
      |                                                   ^~~
sorting.cpp:6:26: error: 'x_moves' was not declared in this scope
    6 |             swap(fin_arr[x_moves[i]], fin_arr[y_moves[i]]);
      |                          ^~~~~~~
sorting.cpp:6:47: error: 'y_moves' was not declared in this scope
    6 |             swap(fin_arr[x_moves[i]], fin_arr[y_moves[i]]);
      |                                               ^~~~~~~
sorting.cpp:6:13: error: 'swap' was not declared in this scope
    6 |             swap(fin_arr[x_moves[i]], fin_arr[y_moves[i]]);
      |             ^~~~
sorting.cpp:10:17: error: 'swap' was not declared in this scope
   10 |                 swap(fin_arr[i], fin_arr[fin_arr[i]]);
      |                 ^~~~
sorting.cpp: In function 'void findSwapPairs(int, int)':
sorting.cpp:13:22: error: 'm' was not declared in this scope
   13 |     int lo = 0, hi = m;
      |                      ^
sorting.cpp:19:5: error: 'x_ans' was not declared in this scope
   19 |     x_ans.resize(lo), y_ans.resize(lo);
      |     ^~~~~
sorting.cpp:19:23: error: 'y_ans' was not declared in this scope
   19 |     x_ans.resize(lo), y_ans.resize(lo);
      |                       ^~~~~
sorting.cpp:20:12: error: expected primary-expression before 'int'
   20 |     vector<int> pos(n);
      |            ^~~
sorting.cpp:22:9: error: 'pos' was not declared in this scope
   22 |         pos[arr[i]] = i;
      |         ^~~
sorting.cpp:22:13: error: 'arr' was not declared in this scope
   22 |         pos[arr[i]] = i;
      |             ^~~
sorting.cpp:24:14: error: 'pos' was not declared in this scope
   24 |         swap(pos[arr[x_moves[i]]], pos[arr[y_moves[i]]]), swap(arr[x_moves[i]], arr[y_moves[i]]),
      |              ^~~
sorting.cpp:24:18: error: 'arr' was not declared in this scope
   24 |         swap(pos[arr[x_moves[i]]], pos[arr[y_moves[i]]]), swap(arr[x_moves[i]], arr[y_moves[i]]),
      |                  ^~~
sorting.cpp:24:22: error: 'x_moves' was not declared in this scope
   24 |         swap(pos[arr[x_moves[i]]], pos[arr[y_moves[i]]]), swap(arr[x_moves[i]], arr[y_moves[i]]),
      |                      ^~~~~~~
sorting.cpp:24:44: error: 'y_moves' was not declared in this scope
   24 |         swap(pos[arr[x_moves[i]]], pos[arr[y_moves[i]]]), swap(arr[x_moves[i]], arr[y_moves[i]]),
      |                                            ^~~~~~~
sorting.cpp:24:9: error: 'swap' was not declared in this scope
   24 |         swap(pos[arr[x_moves[i]]], pos[arr[y_moves[i]]]), swap(arr[x_moves[i]], arr[y_moves[i]]),
      |         ^~~~
sorting.cpp:25:24: error: 'x_todo' was not declared in this scope
   25 |         x_ans[i] = pos[x_todo[i]], y_ans[i] = pos[y_todo[i]],
      |                        ^~~~~~
sorting.cpp:25:51: error: 'y_todo' was not declared in this scope
   25 |         x_ans[i] = pos[x_todo[i]], y_ans[i] = pos[y_todo[i]],
      |                                                   ^~~~~~