Submission #793892

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

towns

#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: In function 'std::vector<std::pair<int, int> > get_swaps(std::vector<int>)':
towns.cpp:10:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   10 |     int n = S.size();
      |             ~~~~~~^~
towns.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
towns.cpp:60:32: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |         if(get_swaps(s).size() <= md+1) b = md;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~~~
towns.cpp:74:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         if(i >= swaps.size()) P[i] = 0, Q[i] = 0;
      |            ~~^~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccUePDU1.o: in function `main':
grader.c:(.text.startup+0x83): undefined reference to `hubDistance(int, int)'
collect2: error: ld returned 1 exit status