제출 #572522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572522		MohamedFaresNebili	정렬하기 (IOI15_sorting)	C++14	74 / 100	1094 ms	18280 KiB

sorting

#include <bits/stdc++.h>
#include "sorting.h"
 
        using namespace std;
 
        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()
 
        bool can(int N, int S[], int M, int X[], int Y[]) {
            int s[N], x[M], y[M];
            int res[N], pos[N], ind[N];
            for(int l = 0; l < N; l++) s[l] = S[l];
            for(int l = 0; l < M; l++)
                x[l] = X[l], y[l] = Y[l];
            for(int l = 0; l < N; l++) {
                res[l] = l; pos[s[l]] = l;
            }
            for(int l = 0; l < M; l++) {
                int i = x[l], j = y[l];
                swap(res[i], res[j]);
            }
            for(int l = 0; l < N; l++)
                ind[res[l]] = l;
            map<int, bool> se;
            for(int l = 0; l < N; l++) {
                if(s[l] == ind[l]) continue;
                se[l] = 1;
            }
            for(int l = 0; l < M; l++) {
                int i = x[l], j = y[l];
                swap(s[i], s[j]);
                swap(pos[s[i]], pos[s[j]]);
                i = ind[i], j = ind[j];
                swap(res[i], res[j]);
                swap(ind[res[i]], ind[res[j]]);
 
                if(se.count(x[l])) se.erase(x[l]);
                if(se.count(y[l])) se.erase(y[l]);
                if(s[x[l]] != ind[x[l]]) se[x[l]] = 1;
                if(s[y[l]] != ind[y[l]]) se[y[l]] = 1;
 
                int u = 0, v = 0;
                if(se.size() != 0) {
                    auto it = se.begin();
                    u = it->first;
                    v = pos[ind[it->first]];
                }
 
                swap(s[u], s[v]);
                swap(pos[s[u]], pos[s[v]]);
 
                if(se.count(u)) se.erase(u);
                if(se.count(v)) se.erase(v);
 
                if(s[u] != ind[u]) se[u] = 1;
                if(s[v] != ind[v]) se[v] = 1;
            }
            for(int l = 0; l < N - 1; l++)
                if(s[l] > s[l + 1]) return 0;
            return 1;
        }
 
        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 md = (lo + hi) / 2;
                if(can(N, S, md, X, Y)) {
                    M = md; hi = md - 1;
                }
                else lo = md + 1;
            }
            int res[N], pos[N], ind[N];
            for(int l = 0; l < N; l++) {
                res[l] = l; pos[S[l]] = l;
            }
            for(int l = 0; l < M; l++) {
                int i = X[l], j = Y[l];
                swap(res[i], res[j]);
            }
            for(int l = 0; l < N; l++)
                ind[res[l]] = l;
            map<int, bool> se;
            for(int l = 0; l < N; l++) {
                if(S[l] == ind[l]) continue;
                se[l] = 1;
            }
            for(int l = 0; l < M; l++) {
                int i = X[l], j = Y[l];
                swap(S[i], S[j]);
                swap(pos[S[i]], pos[S[j]]);
                i = ind[i], j = ind[j];
                swap(res[i], res[j]);
                swap(ind[res[i]], ind[res[j]]);
 
                if(se.count(X[l])) se.erase(X[l]);
                if(se.count(Y[l])) se.erase(Y[l]);
 
                if(S[X[l]] != ind[X[l]]) se[X[l]];
                if(S[Y[l]] != ind[Y[l]]) se[Y[l]];
 
                int u = 0, v = 0;
                if(se.size() != 0) {
                    auto it = se.begin();
                    u = it->first, v = pos[ind[it->first]];
                }
 
                swap(S[u], S[v]);
                swap(pos[S[u]], pos[S[v]]);
 
                P[l] = u, Q[l] = v;
 
                if(se.count(u)) se.erase(u);
                if(se.count(v)) se.erase(v);
 
                if(S[u] != ind[u]) se[u] = 1;
                if(S[v] != ind[v]) se[v] = 1;
            }
            return M;
        }

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