제출 #572538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572538		MohamedFaresNebili	Sorting (IOI15_sorting)	C++14	100 / 100	248 ms	27480 KiB

sorting

#include <bits/stdc++.h>
#include "sorting.h"
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second
        #define lb lower_bound
        #define all(x) (x).begin(), (x).end()

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        vector<ii> ans, ve;
        bool can(int N, int S[], int M, int X[], int Y[]) {
            ve.clear();
            int s[N], pos[N], res[N], arr[N], a[N], x[M], y[M];
            for(int l = 0; l < N; l++) {
                res[l] = l, arr[l] = l; a[l] = l;
                s[l] = S[l]; pos[s[l]] = l;
            }
            for(int l = 0; l < M; l++) {
                x[l] = X[l], y[l] = Y[l];
                swap(res[x[l]], res[y[l]]);
            }
            int c = 0;
            for(int l = 0; l < N; l++) {
                if(res[l] == pos[l]) continue;
                int i = X[c], j = Y[c];
                swap(arr[i], arr[j]);
                swap(a[arr[i]], a[arr[j]]);

                ve.pb({a[pos[l]], a[res[l]]});
                int val = s[res[l]];
                swap(s[pos[l]], s[res[l]]);
                swap(pos[l], pos[val]);
                c++;
            }
            if(c > M) return 0;
            for(int l = c; l < M; l++) ve.pb({0, 0});
            return 1;
        }

        int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
            int lo = 0, hi = N - 1; M = N; ans.clear();
            while(lo <= hi) {
                int md = (lo + hi) / 2;
                if(can(N, S, md, X, Y)) {
                    M = md; hi = md - 1;
                    ans.assign(all(ve));
                }
                else lo = md + 1;
            }
            int l = 0;
            for(auto u : ans) P[l] = u.ff, Q[l++] = u.ss;
            return 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