Submission #654851

#	Time	Username	Problem	Language	Result	Execution time	Memory
654851		benjaminkleyn	Sorting (IOI15_sorting)	C++17	100 / 100	203 ms	19324 KiB

sorting

#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
typedef long long ll;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
    int lo = 0, hi = M;
    vector<int> s(N);
    vector<int> pos(N);
    vector<pair<int,int>> swaps;
    while (true)
    {
        int mid = (lo + hi) / 2;

        for (int i = 0; i < N; i++)
            s[i] = S[i];

        for (int i = 0; i < mid; i++)
            swap(s[X[i]], s[Y[i]]);

        for (int i = 0; i < N; i++)
            pos[s[i]] = i;

        swaps.resize(0);
        for (int i = 0; i < N; i++)
            if (s[i] != i)
            {
                int x = i, y = pos[i];
                swaps.push_back({s[i], i});
                swap(s[x], s[y]);
                pos[s[x]] = x;
                pos[s[y]] = y;
            }

        if (lo == hi)
            break;

        if (swaps.size() <= mid)
            hi = mid;
        else
            lo = mid + 1;
    }

    for (int i = 0; i < N; i++)
        pos[S[i]] = i;

    for (int i = 0; i < swaps.size(); i++)
    {
        swap(pos[S[X[i]]], pos[S[Y[i]]]); 
        swap(S[X[i]], S[Y[i]]);
        P[i] = pos[swaps[i].first], Q[i] = pos[swaps[i].second];
        swap(pos[S[P[i]]], pos[S[Q[i]]]);
        swap(S[P[i]], S[Q[i]]);
    }
    for (int i = swaps.size(); i < hi; i++)
        P[i] = Q[i] = 0;

    return hi;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:39: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]
   39 |         if (swaps.size() <= mid)
      |             ~~~~~~~~~~~~~^~~~~~
sorting.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < swaps.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
sorting.cpp:56:28: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   56 |     for (int i = swaps.size(); i < hi; i++)
      |                  ~~~~~~~~~~^~

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