Submission #793886

#	Time	Username	Problem	Language	Result	Execution time	Memory
793886		Jarif_Rahman	Towns (IOI15_towns)	C++17	Compilation error	0 ms	0 KiB

towns

#include "sorting.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

vector<pair<int, int>> get_swaps(vector<int> S){
    int n = S.size();
    vector<pair<int, int>> swaps;
    vector<int> pos(n);
    for(int i = 0; i < n; i++) pos[S[i]] = i;
    vector<bool> bl(n, 0);

    for(int i = 0; i < n; i++){
        if(bl[S[i]]) continue;
        if(S[i] == i){
            bl[i] = 1;
            continue;
        }
        int j = i;
        while(1){
            if(bl[S[j]]){
                bl[j] = 1;
                break;
            }
            swaps.pb({S[j], j});
            bl[j] = 1;
            j = S[j];
        }

    }

    return swaps;
}

int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]){
    bool sorted = 1;
    for(int i = 0; i < n; i++) sorted&=(S[i] == i);
    if(sorted) return 0;

    int k;
    
    vector<int> s(n);
    for(int i = 0; i < n; i++) s[i] = S[i];

    int a = 0, b = m-1;
    int ls = -1;
    while(a < b){
        int md = (a+b)/2;
        while(ls < md){
            ls++;
            swap(s[X[ls]], s[Y[ls]]);
        }
        while(ls > md){
            swap(s[X[ls]], s[Y[ls]]);
            ls--;
        }
        if(get_swaps(s).size() <= md+1) b = md;
        else a = md+1;
    }

    k = a;

    vector<int> pos(n);
    for(int i = 0; i < n; i++) pos[S[i]] = i;

    auto swaps = get_swaps(s);
    for(int i = 0; i <= k; i++){
        swap(S[X[i]], S[Y[i]]);
        swap(pos[S[X[i]]], pos[S[Y[i]]]);

        if(i >= swaps.size()) P[i] = 0, Q[i] = 0;
        else{
            auto [x, y] = swaps[i];
            swap(pos[x], pos[y]);
            swap(S[pos[x]], S[pos[y]]);
            P[i] = pos[x], Q[i] = pos[y];
        }
    }

    return k+1;
}

Compilation message (stderr)

towns.cpp:1:10: fatal error: sorting.h: No such file or directory
    1 | #include "sorting.h"
      |          ^~~~~~~~~~~
compilation terminated.