Submission #426588

#	Time	Username	Problem	Language	Result	Execution time	Memory
426588		Peti	Sorting (IOI15_sorting)	C++14	100 / 100	212 ms	20668 KiB

sorting

#include <bits/stdc++.h>
#include "sorting.h"

using namespace std;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    vector<int> inv(N);
    for(int i = 0; i < N; i++)
        inv[S[i]] = i;

    int l = -1, r = M+1;
    while(l+1 < r){
        int m = (l+r)/2;
        vector<int> sor(N);
        for(int i = 0; i < N; i++)
            sor[i] = S[i];
        for(int i = 0; i < m; i++)
            swap(sor[X[i]], sor[Y[i]]);

        vector<bool> volt(N, false);
        int kor = 0;
        for(int i = 0; i < N; i++){
            if(volt[i]) continue;
            kor++;
            int x = sor[i];
            volt[i] = true;
            while(x != i){
                volt[x] = true;
                x = sor[x];
            }
        }
        if(N-kor <= m)
            r = m;
        else
            l = m;
    }

    vector<int> S2(N);
    for(int i = 0; i < N; i++)
        S2[i] = S[i];
    for(int i = 0; i < r; i++)
        swap(S[X[i]], S[Y[i]]);

    vector<bool> volt(N, false);
    vector<pair<int, int>> csere;
    for(int i = 0; i < N; i++){
        if(volt[i]) continue;
        int x = S[i];
        vector<int> v;
        while(x != i){
            v.push_back(x);
            volt[x] = true;
            x = S[x];
        }
        volt[i] = true;
        v.push_back(i);
        for(int j = 0; j < (int)v.size()-1; j++)
            csere.push_back(make_pair(v[j], v[j+1]));
    }

    int x = 0;
    for(int i = 0; i < r; i++){
        swap(inv[S2[X[i]]], inv[S2[Y[i]]]);
        swap(S2[X[i]], S2[Y[i]]);
        if(x < csere.size()){
            P[i] = inv[csere[x].first];
            Q[i] = inv[csere[x].second];
            swap(S2[inv[csere[x].first]], S2[inv[csere[x].second]]);
            swap(inv[csere[x].first], inv[csere[x].second]);
            x++;
        } else
            P[i] = Q[i] = 0;
    }

	return r;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:65: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]
   65 |         if(x < csere.size()){
      |            ~~^~~~~~~~~~~~~~

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