Submission #793728

#	Time	Username	Problem	Language	Result	Execution time	Memory
793728		Jarif_Rahman	Sorting (IOI15_sorting)	C++17	74 / 100	1048 ms	18504 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;
    int mn = 1e8;

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

    for(k = 0; k < m; k++){
        swap(s[X[k]], s[Y[k]]);
        if(get_swaps(s).size() <= k+1) break;
    }

    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:52: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]
   52 |         if(get_swaps(s).size() <= k+1) break;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~~
sorting.cpp:63: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]
   63 |         if(i >= swaps.size()) P[i] = 0, Q[i] = 0;
      |            ~~^~~~~~~~~~~~~~~
sorting.cpp:45:9: warning: unused variable 'mn' [-Wunused-variable]
   45 |     int mn = 1e8;
      |         ^~

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