제출 #1136254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136254		byunjaewoo	Swap (BOI16_swap)	C++20	100 / 100	594 ms	180620 KiB

swap

#include <bits/stdc++.h>
using namespace std;

const int N=200010;
int n, a[N];
vector<int> c[N];
vector<vector<int>> d[N];

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    c[1].push_back(a[1]);
    for(int i=1; i<=(n-1)/2; i++) {
        sort(c[i].begin(), c[i].end()), c[i].erase(unique(c[i].begin(), c[i].end()), c[i].end());
        for(int xx:c[i]) {
            int x=xx, y=a[2*i], z=a[2*i+1];
            if(x<y && x<z) {
                c[2*i].push_back(y), c[2*i+1].push_back(z);
                continue;
            }
            if(y<x && y<z) {
                swap(x, y);
                c[2*i].push_back(y), c[2*i+1].push_back(z);
                continue;
            }
            c[2*i].push_back(x), c[2*i+1].push_back(y), c[2*i].push_back(y), c[2*i+1].push_back(x);
        }
    }
    for(int i=1; i<=n; i++) {
        if(i>(n-1)/2) sort(c[i].begin(), c[i].end()), c[i].erase(unique(c[i].begin(), c[i].end()), c[i].end());
        d[i].resize(c[i].size());
    }
    for(int i=n; i>=1; i--) {
        for(int j_=0; j_<c[i].size(); j_++) {
            int xx=c[i][j_];
            if(2*i>n) {
                d[i][j_].push_back(xx);
                continue;
            }
            if(2*i+1>n) {
                d[i][j_].push_back(min(xx, a[2*i])), d[i][j_].push_back(max(xx, a[2*i]));
                continue;
            }
            vector<int> &v=d[i][j_];
            int x=xx, y=a[2*i], z=a[2*i+1];
            if(x<y && x<z) {
                v.push_back(x);
                int p1=lower_bound(c[2*i].begin(), c[2*i].end(), y)-c[2*i].begin();
                int p2=lower_bound(c[2*i+1].begin(), c[2*i+1].end(), z)-c[2*i+1].begin();
                for(int l=1, j=0; ; l*=2) {
                    for(int k=j; k<min((int)d[2*i][p1].size(), j+l); k++) v.push_back(d[2*i][p1][k]);
                    for(int k=j; k<min((int)d[2*i+1][p2].size(), j+l); k++) v.push_back(d[2*i+1][p2][k]);
                    if(j+l-1>=d[2*i][p1].size()) break;
                    j+=l;
                }
                continue;
            }
            if(y<x && y<z) {
                swap(x, y);
                v.push_back(x);
                int p1=lower_bound(c[2*i].begin(), c[2*i].end(), y)-c[2*i].begin();
                int p2=lower_bound(c[2*i+1].begin(), c[2*i+1].end(), z)-c[2*i+1].begin();
                for(int l=1, j=0; ; l*=2) {
                    for(int k=j; k<min((int)d[2*i][p1].size(), j+l); k++) v.push_back(d[2*i][p1][k]);
                    for(int k=j; k<min((int)d[2*i+1][p2].size(), j+l); k++) v.push_back(d[2*i+1][p2][k]);
                    if(j+l-1>=d[2*i][p1].size()) break;
                    j+=l;
                }
                continue;
            }
            vector<int> a(1, z), b(1, z);
            int p1=lower_bound(c[2*i].begin(), c[2*i].end(), y)-c[2*i].begin();
            int p2=lower_bound(c[2*i+1].begin(), c[2*i+1].end(), x)-c[2*i+1].begin();
            for(int l=1, j=0; ; l*=2) {
                for(int k=j; k<min((int)d[2*i][p1].size(), j+l); k++) a.push_back(d[2*i][p1][k]);
                for(int k=j; k<min((int)d[2*i+1][p2].size(), j+l); k++) a.push_back(d[2*i+1][p2][k]);
                if(j+l-1>=d[2*i][p1].size()) break;
                j+=l;
            }
            p1=lower_bound(c[2*i].begin(), c[2*i].end(), x)-c[2*i].begin();
            p2=lower_bound(c[2*i+1].begin(), c[2*i+1].end(), y)-c[2*i+1].begin();
            for(int l=1, j=0; ; l*=2) {
                for(int k=j; k<min((int)d[2*i][p1].size(), j+l); k++) b.push_back(d[2*i][p1][k]);
                for(int k=j; k<min((int)d[2*i+1][p2].size(), j+l); k++) b.push_back(d[2*i+1][p2][k]);
                if(j+l-1>=d[2*i][p1].size()) break;
                j+=l;
            }
            swap(a, v);
            if(b<v) swap(b, v);
        }
        if(2*i+1<=n) d[2*i].clear(), d[2*i+1].clear();
    }
    for(int i:d[1][0]) cout<<i<<" ";
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 32 / 32