oj.uz

Submission #520740

# Submission time Handle Problem Language Result Execution time Memory
520740 2022-01-31T01:01:14 Z christinelynn Swap (BOI16_swap) C++17
100 / 100
 968 ms 232464 KB 
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 2e5 + 9;
const ll inf = 1e9 + 7;
 
vector<ll> dp[N][18][2];
ll n,a[N];
bool need[N][18][2];
 
void Merge(vector<ll> &res,vector<ll> &a,vector<ll> &b){
    for (ll i = 0,j = 1;i < a.size();i += j,j *= 2){
        for (ll k = i;k < i + j && k < a.size();k++) res.push_back(a[k]);
        for (ll k = i;k < i + j && k < b.size();k++) res.push_back(b[k]);
    }
}
 
int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n;
    for (ll i = 1;i <= n;i++) cin>>a[i];
    need[1][0][1] = 1;
 
    for (ll node = 1;node <= n/2;node++){
        for (ll i = 0;node >> i;i++){
            for (auto j : {0,1}){
                if (!need[node][i][j]) continue;
                ll p = ((node >> i + 1) << 1) + j;
                ll mn = min({a[p],a[node*2],a[node*2 + 1]});
                if (mn == a[node*2])
                    need[2*node][i + 1][j] = need[2*node + 1][0][1] = 1;
                else if (mn == a[p])
                    need[2*node][0][0] = need[2*node + 1][0][1] = 1;
                else
                    need[2*node][0][0] = need[2*node + 1][0][0] = 1,
                    need[2*node][i + 1][j] = need[2*node + 1][i + 1][j] = 1;
            }
        }
    }
 
    for (ll node = n;node;node--){
        for (ll i = 0;node >> i;i++){
            for (auto j : {0,1}){
                if (!need[node][i][j]) continue;
 
                ll p = ((node >> i + 1) << 1) + j;
                if (2*node > n) dp[node][i][j] = {a[p]};
                else if (2*node == n) dp[node][i][j] = {min(a[p],a[node*2]),max(a[p],a[node*2])};
                else{
                    ll mn = min({a[p],a[2*node],a[2*node + 1]});
                    if (mn == a[2*node + 1]){
                        vector<ll> tmp1,tmp2; tmp1 = tmp2 = {a[2*node + 1]};
                        Merge(tmp1,dp[2*node][0][0],dp[2*node + 1][i + 1][j]);
                        Merge(tmp2,dp[2*node][i + 1][j],dp[2*node + 1][0][0]);
                        dp[node][i][j] = min(tmp1,tmp2);
                    }
                    else{
                        dp[node][i][j] = {min(a[p],a[2*node])};
                        if (mn == a[p])
                            Merge(dp[node][i][j],dp[2*node][0][0],dp[2*node + 1][0][1]);
                        else
                            Merge(dp[node][i][j],dp[2*node][i + 1][j],dp[2*node + 1][0][1]);
                    }
                }
            }
        }
        if (2*node < n){
            for (ll i = 0;2*node >> i;i++){
                for (auto j : {0,1})
                    vector<ll>().swap(dp[2*node][i][j]),
                    vector<ll>().swap(dp[2*node + 1][i][j]);
            }
        }
    }
    for (auto i : dp[1][0][1]) cout<<i<<" ";
}
 
/* stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?)
  * do smth instead of nothing and stay organized
  * WRITE STUFF DOWN
  * DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

swap.cpp: In function 'void Merge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:17:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (ll i = 0,j = 1;i < a.size();i += j,j *= 2){
      |                         ~~^~~~~~~~~~
swap.cpp:18:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for (ll k = i;k < i + j && k < a.size();k++) res.push_back(a[k]);
      |                                    ~~^~~~~~~~~~
swap.cpp:19:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         for (ll k = i;k < i + j && k < b.size();k++) res.push_back(b[k]);
      |                                    ~~^~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:38:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |                 ll p = ((node >> i + 1) << 1) + j;
      |                                  ~~^~~
swap.cpp:56:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |                 ll p = ((node >> i + 1) << 1) + j;
      |                                  ~~^~~
swap.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 169284 KB Output is correct
2 Correct 75 ms 169352 KB Output is correct
3 Correct 77 ms 169292 KB Output is correct
4 Correct 80 ms 169392 KB Output is correct
5 Correct 76 ms 169308 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 169284 KB Output is correct
2 Correct 75 ms 169352 KB Output is correct
3 Correct 77 ms 169292 KB Output is correct
4 Correct 80 ms 169392 KB Output is correct
5 Correct 76 ms 169308 KB Output is correct
6 Correct 92 ms 169388 KB Output is correct
7 Correct 78 ms 169392 KB Output is correct
8 Correct 80 ms 169268 KB Output is correct
9 Correct 82 ms 169384 KB Output is correct
10 Correct 79 ms 169336 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 169284 KB Output is correct
2 Correct 75 ms 169352 KB Output is correct
3 Correct 77 ms 169292 KB Output is correct
4 Correct 80 ms 169392 KB Output is correct
5 Correct 76 ms 169308 KB Output is correct
6 Correct 92 ms 169388 KB Output is correct
7 Correct 78 ms 169392 KB Output is correct
8 Correct 80 ms 169268 KB Output is correct
9 Correct 82 ms 169384 KB Output is correct
10 Correct 79 ms 169336 KB Output is correct
11 Correct 79 ms 169412 KB Output is correct
12 Correct 79 ms 169460 KB Output is correct
13 Correct 77 ms 169508 KB Output is correct
14 Correct 79 ms 169652 KB Output is correct
15 Correct 89 ms 169796 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 169284 KB Output is correct
2 Correct 75 ms 169352 KB Output is correct
3 Correct 77 ms 169292 KB Output is correct
4 Correct 80 ms 169392 KB Output is correct
5 Correct 76 ms 169308 KB Output is correct
6 Correct 92 ms 169388 KB Output is correct
7 Correct 78 ms 169392 KB Output is correct
8 Correct 80 ms 169268 KB Output is correct
9 Correct 82 ms 169384 KB Output is correct
10 Correct 79 ms 169336 KB Output is correct
11 Correct 79 ms 169412 KB Output is correct
12 Correct 79 ms 169460 KB Output is correct
13 Correct 77 ms 169508 KB Output is correct
14 Correct 79 ms 169652 KB Output is correct
15 Correct 89 ms 169796 KB Output is correct
16 Correct 128 ms 173824 KB Output is correct
17 Correct 127 ms 173792 KB Output is correct
18 Correct 132 ms 173768 KB Output is correct
19 Correct 268 ms 183612 KB Output is correct
20 Correct 268 ms 183464 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 169284 KB Output is correct
2 Correct 75 ms 169352 KB Output is correct
3 Correct 77 ms 169292 KB Output is correct
4 Correct 80 ms 169392 KB Output is correct
5 Correct 76 ms 169308 KB Output is correct
6 Correct 92 ms 169388 KB Output is correct
7 Correct 78 ms 169392 KB Output is correct
8 Correct 80 ms 169268 KB Output is correct
9 Correct 82 ms 169384 KB Output is correct
10 Correct 79 ms 169336 KB Output is correct
11 Correct 79 ms 169412 KB Output is correct
12 Correct 79 ms 169460 KB Output is correct
13 Correct 77 ms 169508 KB Output is correct
14 Correct 79 ms 169652 KB Output is correct
15 Correct 89 ms 169796 KB Output is correct
16 Correct 128 ms 173824 KB Output is correct
17 Correct 127 ms 173792 KB Output is correct
18 Correct 132 ms 173768 KB Output is correct
19 Correct 268 ms 183612 KB Output is correct
20 Correct 268 ms 183464 KB Output is correct
21 Correct 331 ms 186904 KB Output is correct
22 Correct 305 ms 186836 KB Output is correct
23 Correct 325 ms 186892 KB Output is correct
24 Correct 926 ms 232464 KB Output is correct
25 Correct 968 ms 232424 KB Output is correct