Submission #1182370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182370		rorro	Sorting (IOI15_sorting)	C++20	100 / 100	186 ms	13952 KiB

sorting

#define debug 0

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

//int N, *S, M, *X, *Y, *P, *Q;
int n;
int *A, *D, *ID, *IA; //actual, dest, in d, in a

void print_state() {
        if (!debug)
                return;
        std::cerr << "D[i]:\n";
        for (int i = 0; i < n; ++i) std::cerr << D[i] << ' ';
        std::cerr << "\nID:\n";
        for (int i = 0; i < n; ++i) std::cerr << ID[i] << ' ';
        std::cerr << "\nA:\n";
        for (int i = 0; i < n; ++i) std::cerr << A[i] << ' ';
        std::cerr << "\nIA:\n";
        for (int i = 0; i < n; ++i) std::cerr << IA[i] << ' ';
        std::cerr << '\n';
}

inline bool check(int mid, int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
        if (debug) std::cerr << "entering check function\n\n\n\n\n\n\n";

        if (D == NULL)
                D  = (int*)(malloc(sizeof(int) * N));
        if (A == NULL)
                A  = (int*)(malloc(sizeof(int) * N));
        if (ID == NULL)
                ID = (int*)(malloc(sizeof(int) * N));
        if (IA == NULL)
                IA = (int*)(malloc(sizeof(int) * N));

        for (int i = 0; i < N; ++i) {
                A[i] = S[i];
                D[i] = i;
        }
        for (int i = mid-1; i >= 0; --i)
                std::swap(D[X[i]], D[Y[i]]);

        for (int i = 0; i < N; ++i) {
                ID[D[i]] = i;
                IA[A[i]] = i;
        }

        if (debug) {
                std::cerr << "this is the initial state of the simulation, mid " << mid << " ";
                print_state();
        }

        int j = 0;

        for (int i = 0; i < mid; ++i) {
                if (debug)
                        std::cerr << "forced swap: " << X[i] << ' ' << Y[i] << '\n';
                std::swap( A[X[i]],  A[Y[i]]);
                std::swap(IA[A[X[i]]], IA[A[Y[i]]]);
                std::swap( D[X[i]],  D[Y[i]]);
                std::swap(ID[D[X[i]]], ID[D[Y[i]]]);
                if (debug) {
                        std::cerr << "this is the state after forced swap:\n";
                        print_state();
                }

                bool f = false;

                while (j < N) {
                        int k = IA[j++];
                        if (A[k] != D[k]) {
                                if (debug) std::cerr << "swapping " << k << ' ' << ID[A[k]] << '\n';
                                P[i] = k;
                                Q[i] = ID[A[k]];
                                std::swap(IA[A[P[i]]], IA[A[Q[i]]]);
                                std::swap( A[P[i]],  A[Q[i]]);
                                //std::swap(IA[A[k]], IA[A[ID[A[k]]]]);
                                f = true;
                                break;
                        }

                }

                if (f == false) {
                        if (debug)
                                std::cerr << "no swap\n";
                        P[i] = Q[i] = 0;
                }
                if (debug) {
                        std::cerr << "this is the state after my swap:\n";
                        print_state();
                }
        }

        for (int i = 0; i < N; ++i)
                if (A[i] != i)
                        return false;
        return true;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
        n = N;
        int lo = 0, hi = M;
        while (lo < hi) {
                int mid = (lo+hi)/2;
                if (check(mid, N, S, M, X, Y, P, Q))
                        hi = mid;
                else
                        lo = mid+1;
        }
        check(lo, N, S, M, X, Y, P, Q);
        return lo;
}

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