Submission #484620

# Submission time Handle Problem Language Result Execution time Memory
484620 2021-11-04T19:47:19 Z couplefire Sorting (IOI15_sorting) C++17
0 / 100
1 ms 460 KB
#include <bits/stdc++.h>
using namespace std;

int findSwapPairs(int n, int arr[], int m, int x_moves[], int y_moves[], int x_ans[], int y_ans[]){
    vector<int> fin_arr, x_todo, y_todo;
    auto calc = [&](int mid)->int{
        x_todo.clear(); y_todo.clear();
        for(int i = 0; i<n; ++i) fin_arr[i] = arr[i];
        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 (int)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);
    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]]);
    return lo;
}
# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -