Submission #432513

#	Time	Username	Problem	Language	Result	Execution time	Memory
432513		snasibov05	Sorting (IOI15_sorting)	C++14	54 / 100	1065 ms	76888 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) {
        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[i];
        vector<int> arr = v[i];
        vector<pii> swaps;

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

        if (swaps.size() > i) continue;

        arr = v[i];

        for (int j = 0; j < m; ++j) {
            p[i] = q[i] = 0;
        }

        int k = swaps.size();
        for (int l = 1; l <= k; ++l){
            if (is_sorted(v[l].begin(), v[l].end())) return l;

            int a = idx[l][arr[swaps[l-1].f]];
            int b = idx[l][arr[swaps[l-1].s]];
            p[l-1] = a, q[l-1] = b;
            swap(idx[l][arr[swaps[l-1].f]], idx[l][arr[swaps[l-1].s]]);
            swap(v[l][a], v[l][b]);
            swap(arr[swaps[l-1].f], arr[swaps[l-1].s]);

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

            for (int j = l+1; j <= i; ++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]]);
            }
        }

        return i;
    }

    assert(false);

}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:43:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |         if (swaps.size() > i) continue;
      |             ~~~~~~~~~~~~~^~~
sorting.cpp:51:27: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   51 |         int k = swaps.size();
      |                 ~~~~~~~~~~^~

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