Submission #432297

#	Time	Username	Problem	Language	Result	Execution time	Memory
432297		snasibov05	Sorting (IOI15_sorting)	C++14	20 / 100	1101 ms	76840 KiB

sorting

#include "sorting.h"
#include <vector>
#include <cassert>
#include <algorithm>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second
#define pb push_back

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {

    vector<vector<int>> v(m+1, vector<int>(n));
    vector<vector<int>> idx(m+1, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        v[0][i] = s[i];
        idx[0][s[i]] = i;
    }

    if (is_sorted(v[0].begin(), v[0].end())) return 0;

    for (int i = 1; i <= m; ++i) {
        p[i-1] = q[i-1] = 0;
        v[i] = v[i-1];
        idx[i] = idx[i-1];
        swap(idx[i][v[i][x[i-1]]], idx[i][v[i][y[i-1]]]);
        swap(v[i][x[i-1]], v[i][y[i-1]]);
    }

    vector<int> final = idx[m];
    vector<int> arr = v[m];
    vector<pii> swaps;

    for (int i = 0; i < n; ++i) {
        if (final[i] == i) continue;
        int k = final[i];
        swaps.pb({i, k});
        final[arr[i]] = k;
        arr[k] = arr[i];
        arr[i] = i;
    }

    assert(is_sorted(arr.begin(), arr.end()));

    arr = v[m];

    int k = swaps.size();
    for (int i = 1; i <= k; ++i){
        if (is_sorted(v[i].begin(), v[i].end())) return i;
        
        int a = idx[i][arr[swaps[i-1].f]];
        int b = idx[i][arr[swaps[i-1].s]];
        p[i-1] = a, q[i-1] = b;
        swap(idx[i][arr[swaps[i-1].f]], idx[i][arr[swaps[i-1].s]]);
        swap(v[i][a], v[i][b]);
        swap(arr[swaps[i-1].f], arr[swaps[i-1].s]);

        if (is_sorted(v[i].begin(), v[i].end())) return i;

        for (int j = i+1; j <= m; ++j) {
            v[j] = v[j-1];
            idx[j] = idx[j-1];
            swap(idx[j][v[j][x[j-1]]], idx[j][v[j][y[j-1]]]);
            swap(v[j][x[j-1]], v[j][y[j-1]]);
        }
    }

    assert(is_sorted(v[m].begin(), v[m].end()));

    return m;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:49:23: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   49 |     int k = swaps.size();
      |             ~~~~~~~~~~^~

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