Submission #793916

#	Time	Username	Problem	Language	Result	Execution time	Memory
793916		Jarif_Rahman	Sorting (IOI15_sorting)	C++17	20 / 100	1 ms	340 KiB

sorting

#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;
    while(ls < ls){
        ls++;
        swap(s[X[ls]], s[Y[ls]]);
    }
    while(ls > ls){
        swap(s[X[ls]], s[Y[ls]]);
        ls--;
    }

    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)

sorting.cpp: In function 'std::vector<std::pair<int, int> > get_swaps(std::vector<int>)':
sorting.cpp:11:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   11 |     int n = S.size();
      |             ~~~~~~^~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:61: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]
   61 |         if(get_swaps(s).size() <= md+1) b = md;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~~~
sorting.cpp:66:14: warning: self-comparison always evaluates to false [-Wtautological-compare]
   66 |     while(ls < ls){
      |           ~~ ^ ~~
sorting.cpp:70:14: warning: self-comparison always evaluates to false [-Wtautological-compare]
   70 |     while(ls > ls){
      |           ~~ ^ ~~
sorting.cpp:83: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]
   83 |         if(i >= swaps.size()) P[i] = 0, Q[i] = 0;
      |            ~~^~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26