Submission #471758

#	Time	Username	Problem	Language	Result	Execution time	Memory
471758		blue	정렬하기 (IOI15_sorting)	C++17	100 / 100	209 ms	24076 KiB

sorting

#include "sorting.h"
#include <vector>
#include <queue>
#include <iostream>
using namespace std;


const int maxN = 200'000;

int N;
vector<int> S(maxN);

int M;
int* X;
int* Y;

int* P;
int* Q;

vector<int> T(maxN);
vector<bool> visit(maxN);

int binary_search(int l, int r)
{
    // cerr << "search " << l << ' ' << r << '\n';
    if(l == r)
    {
        vector<int> act1, act2;

        T = S;
        for(int j = 0; j < l; j++)
            swap(T[ X[j] ], T[ Y[j] ]);

        // cerr << "final: ";
        // for(int i = 0; i < N; i++) cerr << T[i] << ' ';
        // cerr << '\n';

        vector<int> num1, num2;

        for(int i = 0; i < N; i++)
        {
            int u, v;
            u = i;
            v = T[u];
            // cerr << u << v << '\n';
            while(1)
            {
                if(u == v) break;

                swap(T[u], T[v]);
                act1.push_back(u);
                act2.push_back(v);

                num1.push_back(T[u]);
                num2.push_back(T[v]);

                // cerr << "act swap " << u << ' ' << v << '\n';

                u = T[u];
                v = T[u];
            }
        }


        vector<int> real(N);
        for(int i = 0; i < N; i++) real[i] = i;

        vector<int> Z(N);
        for(int i = 0; i < N; i++) Z[i] = S[i];
        vector<int> Zpos(N);
        for(int i = 0; i < N; i++) Zpos[ Z[i] ] = i;

        for(int j = 0; j < l; j++)
        {
            swap(Z[ X[j] ], Z[ Y[j] ]);
            swap(Zpos[ Z[ X[j] ] ], Zpos[ Z[ Y[j] ] ]);

            swap(Z[ Zpos[ num1[j] ] ], Z[ Zpos[ num2[j] ] ]);
            swap(Zpos[ num1[j] ], Zpos[ num2[j] ]);
            P[j] = Zpos[ num1[j] ];
            Q[j] = Zpos[ num2[j] ];
        }

        // for(int j = l-1; j >= 0; j--)
        // {
        //     // cerr << "j = " << j << '\n';
        //     // cerr << act1[j] << ' ' << act2[j] << '\n';
        //
        //     // for(int i = 0; i < N; i++) cerr << real[i] << ' ';
        //     // cerr << '\n';
        //     // cerr << "done\n";
        //
        //     P[j] = real[ act1[j] ];
        //     Q[j] = real[ act2[j] ];
        //     swap(real[ X[j] ], real[ Y[j] ]);
        // }


        // cerr << "sequence after unadjusted sorting: ";
        // for(int i = 0; i < N; i++) cerr << T[i] << ' ';
        // cerr << '\n';

        vector<int> fin = S;
        for(int j = 0; j < l; j++)
        {
            swap(fin[ X[j] ], fin[ Y[j] ]);
            swap(fin[ P[j] ], fin[ Q[j] ]);
        }
        // cerr << "sequence after sorting: ";
        // for(int i = 0; i < N; i++) cerr << fin[i] << ' ';
        // cerr << '\n';


        return l;
    }
    else
    {
        int m = (l+r)/2;

        T = S;

        for(int j = 0; j < m; j++)
        {
            swap(T[ X[j] ], T[ Y[j] ]);
        }

        for(int i = 0; i < N; i++) visit[i] = 0;
        int ct = 0;
        for(int i = 0; i < N; i++)
        {
            if(visit[i]) continue;
            ct++;

            visit[i] = 1;
            for(int j = T[i]; j != i; j = T[j])
                visit[j] = 1;
        }

        if(N - ct <= m)
            return binary_search(l, m);
        else
            return binary_search(m+1, r);
    }
}

int findSwapPairs(int N_, int S_[], int M_, int X_[], int Y_[], int P_[], int Q_[])
{
    N = N_;
    for(int i = 0; i < N; i++) S[i] = S_[i];

    M = M_;
    X = X_;
    Y = Y_;

    P = P_;
    Q = Q_;

    return binary_search(0, M);
}

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