Submission #646211

#	Time	Username	Problem	Language	Result	Execution time	Memory
646211		fatemetmhr	Swap (BOI16_swap)	C++17	100 / 100	245 ms	75752 KiB

swap

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x)  x.begin(), x.end()
#define pb      push_back
#define fi      first
#define se      second

const int maxn5 = 3e5 + 10;

int n;
vector <int> av[maxn5], tochil[maxn5], ans[maxn5];
int a[maxn5];

void solve(int v){
    if(v * 2 + 1 > n){
        if(v * 2 > n){
            av[v].pb(n + 1);
            ans[v].pb(0);
            return;
        }
        solve(v * 2);
        int i = 0;
        while(av[v * 2][i] < a[v * 2]){
            av[v].pb(av[v * 2][i]);
            ans[v].pb(0);
            tochil[v].pb(0);
            i++;
        }
        ans[v].pb(0);
        tochil[v].pb(0);
        av[v].pb(a[v * 2]);
        while(i < av[v * 2].size()){
            ans[v].pb(ans[v * 2][i] + 1);
            tochil[v].pb(1);
            av[v].pb(av[v * 2][i++]);
        }
        return;
    }
    solve(v * 2); solve(v * 2 + 1);
    int id1 = 0, id2 = 0;
    int re = 0;
    while(id1 < av[v * 2].size() || id2 < av[v * 2 + 1].size()){
        if(id1 < av[v * 2].size() && (id2 == av[v * 2 + 1].size() || av[v * 2][id1] < av[v * 2 + 1][id2]))
            av[v].pb(av[v * 2][id1++]);
        else
            av[v].pb(av[v * 2 + 1][id2++]);
        if(re == 0 && av[v].back() > min(a[v * 2], a[v * 2 + 1])){
            re = 1;
            int tmp = av[v].back();
            av[v][av[v].size() - 1] = min(a[v * 2], a[v * 2 + 1]);
            av[v].pb(tmp);
        }
        if(re == 1 && av[v].back() > max(a[v * 2], a[v * 2 + 1])){
            re = 2;
            int tmp = av[v].back();
            av[v][av[v].size() - 1] = max(a[v * 2], a[v * 2 + 1]);
            av[v].pb(tmp);
        }
    }
    av[v].pop_back();
    int pt32 = upper_bound(all(av[v * 2 + 1]), a[v * 2]) - av[v * 2 + 1].begin();
    int pt33 = upper_bound(all(av[v * 2 + 1]), a[v * 2 + 1]) - av[v * 2 + 1].begin();
    int pt22 = upper_bound(all(av[v * 2]), a[v * 2]) - av[v * 2].begin();
    id1 = 0; id2 = 0;
    for(int i = 0; i < av[v].size(); i++){
        while(av[v * 2][id1] < av[v][i])
            id1++;
        while(av[v * 2 + 1][id2] < av[v][i])
            id2++;
        int val1 = av[v][i] - 1, val2 = a[v * 2], val3 = a[v * 2 + 1];
        if(i > 0 && val1 == av[v][i - 1]){
            ans[v].pb(-1);
            tochil[v].pb(-1);
            continue;
        }
        if(val1 < min(val2, val3)){
            ans[v].pb(0);
            tochil[v].pb(0);
        }
        if(val2 < min(val1, val3)){
            ans[v].pb(ans[v * 2][id1] + 1);
            tochil[v].pb(1);
        }
        if(val3 < min(val1, val2)){
            if(val1 < val2){
                if(ans[v * 2][id1] <= ans[v * 2 + 1][id2]){
                    ans[v].pb(ans[v * 2][id1] + 1);
                    tochil[v].pb(3);
                }
                else{
                    ans[v].pb(ans[v * 2 + 1][id2] + 1);
                    tochil[v].pb(2);
                }
            }
            else{
                if(ans[v * 2][pt22] <= ans[v * 2 + 1][pt32]){
                    ans[v].pb(ans[v * 2 + 1][id2] + 1);
                    tochil[v].pb(2);
                }
                else{
                    ans[v].pb(ans[v * 2][id1] + 1);
                    tochil[v].pb(3);
                }
            }
        }
        //cout << "check out " << v << ' ' << i << ' ' << tochil[v].size() << ' ' << val1 << ' ' << val2 << ' ' << val3 << endl;
    }
    return;
}


void find_ans(int v){
    if(v * 2 > n)
        return;
    int pt = upper_bound(all(av[v]), a[v]) - av[v].begin();
    //cout << "aha " << v << ' ' << av[v].size() << ' ' << tochil[v].size() << ' ' << a[v] << ' ' << pt << endl;
    if(tochil[v][pt] == 1)
        swap(a[v], a[v * 2]);
    if(tochil[v][pt] == 2)
        swap(a[v], a[v * 2 + 1]);
    if(tochil[v][pt] == 3){
        swap(a[v], a[v * 2]);
        swap(a[v], a[v * 2 + 1]);
    }
    find_ans(v * 2);
    if(v * 2 + 1 <= n)
        find_ans(v * 2 + 1);
    return;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    solve(1);
    find_ans(1);
    for(int i = 1; i <= n; i++)
        cout << a[i] << ' ';
    cout << endl;
}

Compilation message (stderr)

swap.cpp: In function 'void solve(int)':
swap.cpp:36:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while(i < av[v * 2].size()){
      |               ~~^~~~~~~~~~~~~~~~~~
swap.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     while(id1 < av[v * 2].size() || id2 < av[v * 2 + 1].size()){
      |           ~~~~^~~~~~~~~~~~~~~~~~
swap.cpp:46:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     while(id1 < av[v * 2].size() || id2 < av[v * 2 + 1].size()){
      |                                     ~~~~^~~~~~~~~~~~~~~~~~~~~~
swap.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if(id1 < av[v * 2].size() && (id2 == av[v * 2 + 1].size() || av[v * 2][id1] < av[v * 2 + 1][id2]))
      |            ~~~~^~~~~~~~~~~~~~~~~~
swap.cpp:47:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if(id1 < av[v * 2].size() && (id2 == av[v * 2 + 1].size() || av[v * 2][id1] < av[v * 2 + 1][id2]))
      |                                       ~~~~^~~~~~~~~~~~~~~~~~~~~~~
swap.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i = 0; i < av[v].size(); i++){
      |                    ~~^~~~~~~~~~~~~~
swap.cpp:66:9: warning: unused variable 'pt33' [-Wunused-variable]
   66 |     int pt33 = upper_bound(all(av[v * 2 + 1]), a[v * 2 + 1]) - av[v * 2 + 1].begin();
      |         ^~~~

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