oj.uz

Submission #520736

# Submission time Handle Problem Language Result Execution time Memory
520736 2022-01-31T00:53:02 Z christinelynn Swap (BOI16_swap) C++17
100 / 100
 934 ms 232676 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 78 ms 169344 KB Output is correct
2 Correct 80 ms 169392 KB Output is correct
3 Correct 78 ms 169328 KB Output is correct
4 Correct 75 ms 169384 KB Output is correct
5 Correct 79 ms 169332 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 169344 KB Output is correct
2 Correct 80 ms 169392 KB Output is correct
3 Correct 78 ms 169328 KB Output is correct
4 Correct 75 ms 169384 KB Output is correct
5 Correct 79 ms 169332 KB Output is correct
6 Correct 78 ms 169400 KB Output is correct
7 Correct 78 ms 169400 KB Output is correct
8 Correct 83 ms 169324 KB Output is correct
9 Correct 82 ms 169288 KB Output is correct
10 Correct 80 ms 169328 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 169344 KB Output is correct
2 Correct 80 ms 169392 KB Output is correct
3 Correct 78 ms 169328 KB Output is correct
4 Correct 75 ms 169384 KB Output is correct
5 Correct 79 ms 169332 KB Output is correct
6 Correct 78 ms 169400 KB Output is correct
7 Correct 78 ms 169400 KB Output is correct
8 Correct 83 ms 169324 KB Output is correct
9 Correct 82 ms 169288 KB Output is correct
10 Correct 80 ms 169328 KB Output is correct
11 Correct 100 ms 169396 KB Output is correct
12 Correct 97 ms 169432 KB Output is correct
13 Correct 84 ms 169472 KB Output is correct
14 Correct 80 ms 169616 KB Output is correct
15 Correct 80 ms 169676 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 169344 KB Output is correct
2 Correct 80 ms 169392 KB Output is correct
3 Correct 78 ms 169328 KB Output is correct
4 Correct 75 ms 169384 KB Output is correct
5 Correct 79 ms 169332 KB Output is correct
6 Correct 78 ms 169400 KB Output is correct
7 Correct 78 ms 169400 KB Output is correct
8 Correct 83 ms 169324 KB Output is correct
9 Correct 82 ms 169288 KB Output is correct
10 Correct 80 ms 169328 KB Output is correct
11 Correct 100 ms 169396 KB Output is correct
12 Correct 97 ms 169432 KB Output is correct
13 Correct 84 ms 169472 KB Output is correct
14 Correct 80 ms 169616 KB Output is correct
15 Correct 80 ms 169676 KB Output is correct
16 Correct 139 ms 174128 KB Output is correct
17 Correct 171 ms 174064 KB Output is correct
18 Correct 135 ms 173964 KB Output is correct
19 Correct 268 ms 183924 KB Output is correct
20 Correct 253 ms 183832 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 169344 KB Output is correct
2 Correct 80 ms 169392 KB Output is correct
3 Correct 78 ms 169328 KB Output is correct
4 Correct 75 ms 169384 KB Output is correct
5 Correct 79 ms 169332 KB Output is correct
6 Correct 78 ms 169400 KB Output is correct
7 Correct 78 ms 169400 KB Output is correct
8 Correct 83 ms 169324 KB Output is correct
9 Correct 82 ms 169288 KB Output is correct
10 Correct 80 ms 169328 KB Output is correct
11 Correct 100 ms 169396 KB Output is correct
12 Correct 97 ms 169432 KB Output is correct
13 Correct 84 ms 169472 KB Output is correct
14 Correct 80 ms 169616 KB Output is correct
15 Correct 80 ms 169676 KB Output is correct
16 Correct 139 ms 174128 KB Output is correct
17 Correct 171 ms 174064 KB Output is correct
18 Correct 135 ms 173964 KB Output is correct
19 Correct 268 ms 183924 KB Output is correct
20 Correct 253 ms 183832 KB Output is correct
21 Correct 317 ms 187584 KB Output is correct
22 Correct 318 ms 187604 KB Output is correct
23 Correct 311 ms 187604 KB Output is correct
24 Correct 921 ms 232676 KB Output is correct
25 Correct 934 ms 232416 KB Output is correct