제출 #1182335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182335		rorro	정렬하기 (IOI15_sorting)	C++20	0 / 100	2 ms	1352 KiB

sorting

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

//int N, *S, M, *X, *Y, *P, *Q;
int *A, *D, *ID; //actual, dest, in a
std::deque<int> d;

void do_swap(int i, int j) {
        std::swap(D[i], D[j]);
        std::swap(A[i], A[j]);
        std::swap(ID[i], ID[j]);
        d.push_front(i);
        d.push_front(j);
}

inline bool check(int mid, int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {

        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));

        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;
        }

        for (int i = 0; i < N; ++i)
                d.emplace_back(i);

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

                bool f = false;

                while (!d.empty()) {
                        int k = d.front();
                        d.pop_front();
                        if (A[k] != D[k]) { //trzeba swapnac
                                do_swap(k, ID[k]);
                                f = true;
                                break;
                        }
                }

                if (!f)
                        P[i] = Q[i] = 0;
        }

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

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
        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: 0 / 8
• Subtask 2: 0 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26