oj.uz

Submission #646211

# Submission time Handle Problem Language Result Execution time Memory
646211 2022-09-29T07:52:20 Z fatemetmhr Swap (BOI16_swap) C++17
100 / 100
 245 ms 75752 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21460 KB Output is correct
2 Correct 11 ms 21468 KB Output is correct
3 Correct 10 ms 21440 KB Output is correct
4 Correct 11 ms 21464 KB Output is correct
5 Correct 10 ms 21360 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21460 KB Output is correct
2 Correct 11 ms 21468 KB Output is correct
3 Correct 10 ms 21440 KB Output is correct
4 Correct 11 ms 21464 KB Output is correct
5 Correct 10 ms 21360 KB Output is correct
6 Correct 11 ms 21508 KB Output is correct
7 Correct 10 ms 21428 KB Output is correct
8 Correct 10 ms 21460 KB Output is correct
9 Correct 11 ms 21460 KB Output is correct
10 Correct 10 ms 21464 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21460 KB Output is correct
2 Correct 11 ms 21468 KB Output is correct
3 Correct 10 ms 21440 KB Output is correct
4 Correct 11 ms 21464 KB Output is correct
5 Correct 10 ms 21360 KB Output is correct
6 Correct 11 ms 21508 KB Output is correct
7 Correct 10 ms 21428 KB Output is correct
8 Correct 10 ms 21460 KB Output is correct
9 Correct 11 ms 21460 KB Output is correct
10 Correct 10 ms 21464 KB Output is correct
11 Correct 11 ms 21588 KB Output is correct
12 Correct 11 ms 21588 KB Output is correct
13 Correct 11 ms 21588 KB Output is correct
14 Correct 11 ms 21588 KB Output is correct
15 Correct 11 ms 21588 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21460 KB Output is correct
2 Correct 11 ms 21468 KB Output is correct
3 Correct 10 ms 21440 KB Output is correct
4 Correct 11 ms 21464 KB Output is correct
5 Correct 10 ms 21360 KB Output is correct
6 Correct 11 ms 21508 KB Output is correct
7 Correct 10 ms 21428 KB Output is correct
8 Correct 10 ms 21460 KB Output is correct
9 Correct 11 ms 21460 KB Output is correct
10 Correct 10 ms 21464 KB Output is correct
11 Correct 11 ms 21588 KB Output is correct
12 Correct 11 ms 21588 KB Output is correct
13 Correct 11 ms 21588 KB Output is correct
14 Correct 11 ms 21588 KB Output is correct
15 Correct 11 ms 21588 KB Output is correct
16 Correct 60 ms 33860 KB Output is correct
17 Correct 60 ms 33920 KB Output is correct
18 Correct 60 ms 33912 KB Output is correct
19 Correct 50 ms 33860 KB Output is correct
20 Correct 57 ms 33976 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21460 KB Output is correct
2 Correct 11 ms 21468 KB Output is correct
3 Correct 10 ms 21440 KB Output is correct
4 Correct 11 ms 21464 KB Output is correct
5 Correct 10 ms 21360 KB Output is correct
6 Correct 11 ms 21508 KB Output is correct
7 Correct 10 ms 21428 KB Output is correct
8 Correct 10 ms 21460 KB Output is correct
9 Correct 11 ms 21460 KB Output is correct
10 Correct 10 ms 21464 KB Output is correct
11 Correct 11 ms 21588 KB Output is correct
12 Correct 11 ms 21588 KB Output is correct
13 Correct 11 ms 21588 KB Output is correct
14 Correct 11 ms 21588 KB Output is correct
15 Correct 11 ms 21588 KB Output is correct
16 Correct 60 ms 33860 KB Output is correct
17 Correct 60 ms 33920 KB Output is correct
18 Correct 60 ms 33912 KB Output is correct
19 Correct 50 ms 33860 KB Output is correct
20 Correct 57 ms 33976 KB Output is correct
21 Correct 242 ms 75728 KB Output is correct
22 Correct 241 ms 75668 KB Output is correct
23 Correct 245 ms 75752 KB Output is correct
24 Correct 198 ms 75712 KB Output is correct
25 Correct 197 ms 75712 KB Output is correct