Submission #105053

#	Time	Username	Problem	Language	Result	Execution time	Memory
105053		Alexa2001	Sorting (IOI15_sorting)	C++17	100 / 100	722 ms	29380 KiB

sorting

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

using namespace std;

const int Nmax = 2e5 + 5;

bool used[Nmax];
int p[Nmax], P[Nmax], A[Nmax], wA[Nmax], B[Nmax], wB[Nmax], wp[Nmax];


vector< pair<int,int> > get_moves(int n, int p[])
{
    int i;
    for(i=0; i<n; ++i) used[i] = 0;
    vector< pair<int,int> > mv;

    for(i=0; i<n; ++i)
        if(!used[i])
        {
            int x = i;
            vector<int> cycle;

            do
            {
                used[x] = 1;
                cycle.push_back(x);
                x = p[x];
            }
            while(!used[x]);

            for(int j = 0; j + 1 < cycle.size(); ++j)
                mv.push_back({p[cycle[j]], p[cycle[j+1]]});
        }
    return mv;
}

bool check(int n, int m, int S[], int x[], int y[], int op1[], int op2[])
{
    int i;
    for(i=0; i<n; ++i) p[i] = i, wp[i] = i;
    for(i=0; i<m; ++i)
    {
        int id1, id2;
        id1 = wp[x[i]]; id2 = wp[y[i]];
        swap(wp[p[id1]], wp[p[id2]]);
        swap(p[id1], p[id2]);
    }

    for(i=0; i<n; ++i) P[p[i]] = S[i];

    auto o = get_moves(n, P);

    if(o.size() > m) return 0;
    o.resize(m);

    for(i=0; i<n; ++i) A[i] = wA[i] = i, B[i] = S[i], wB[S[i]] = i;

    for(i=0; i<m; ++i)
    {
        int id1, id2;

        id1 = wA[x[i]]; id2 = wA[y[i]];

        swap(wA[A[id1]], wA[A[id2]]);
        swap(A[id1], A[id2]);

        tie(id1, id2) = o[i];
        id1 = wB[id1]; id2 = wB[id2];

        op1[i] = A[id1];
        op2[i] = A[id2];

        swap(wB[B[id1]], wB[B[id2]]);
        swap(B[id1], B[id2]);
    }
    return 1;
}


int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
    int st, dr, mid;

    st = 0; dr = M;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(check(N, mid, S, X, Y, P, Q)) dr = mid - 1;
            else st = mid + 1;
    }

    check(N, st, S, X, Y, P, Q);

    return st;
}

Compilation message (stderr)

sorting.cpp: In function 'std::vector<std::pair<int, int> > get_moves(int, int*)':
sorting.cpp:12:49: warning: declaration of 'p' shadows a global declaration [-Wshadow]
 vector< pair<int,int> > get_moves(int n, int p[])
                                                 ^
sorting.cpp:9:5: note: shadowed declaration is here
 int p[Nmax], P[Nmax], A[Nmax], wA[Nmax], B[Nmax], wB[Nmax], wp[Nmax];
     ^
sorting.cpp:32:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j + 1 < cycle.size(); ++j)
                            ~~~~~~^~~~~~~~~~~~~~
sorting.cpp: In function 'bool check(int, int, int*, int*, int*, int*, int*)':
sorting.cpp:54:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(o.size() > m) return 0;
        ~~~~~~~~~^~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:81:76: warning: declaration of 'P' shadows a global declaration [-Wshadow]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
                                                                            ^
sorting.cpp:9:14: note: shadowed declaration is here
 int p[Nmax], P[Nmax], A[Nmax], wA[Nmax], B[Nmax], wB[Nmax], wp[Nmax];
              ^

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