oj.uz

Submission #199055

# Submission time Handle Problem Language Result Execution time Memory
199055 2020-01-28T20:10:32 Z stefdasca Swap (BOI16_swap) C++14
100 / 100
 883 ms 231288 KB 
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier 1

using namespace std;

typedef long long ll;

int n, a[200002];
vector<int> dp[200002][36], v1, v2;
bool v[200002][36];

void mrg(vector<int> &v, vector<int> &a, vector<int> &b)
{
    for(int stp=1, i=0, j=0; i<a.size() || j<b.size(); i+=stp, j+=stp, stp*=2)
    {
        for(int k = 0; k < stp && i+k < a.size(); ++k)
            v.push_back(a[i+k]);
        for(int k = 0; k < stp && j+k < b.size(); ++k)
            v.push_back(b[j+k]);
    }
}
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    v[1][0] = 1;
    for(int i = 1; 2 * i + 1 <= n; ++i)
        for(int j = 0; j < 36; ++j)
        {
            if(!v[i][j])
                continue;
            int b = (i >> (j / 2)) ^ (j & 1);
            if(a[2*i+1] < a[b] && a[2*i+1] < a[2*i])
                v[2*i][0] = v[2*i+1][j+2] = v[2*i][j+2] = v[2*i+1][1]=1;
            else
                v[2*i][(j+2) * (a[b] > a[2*i])] = v[2*i+1][0] = 1;
        }
    for(int i = n; i >= 1; --i)
    {
        for(int j = 0; j < 36; ++j)
        {
            if(!v[i][j])
                continue;
            int b = (i >> (j / 2)) ^ (j & 1);
            if(2 * i + 1 <= n)
            {
                if(a[2*i+1] < a[b] && a[2*i+1] < a[2*i])
                {
                    v1 = {a[2*i+1]};
                    v2 = {a[2*i+1]};
                    mrg(v1, dp[2*i][0], dp[2*i+1][j+2]);
                    mrg(v2, dp[2*i][j+2], dp[2*i+1][1]);
                    dp[i][j] = min(v1, v2);
                }
                else
                {
                    dp[i][j] = {min(a[b], a[2*i])};
                    mrg(dp[i][j], dp[2*i][(j+2) * (a[b]>a[2*i])], dp[2*i+1][0]);
                }
            }
            else
                if(2 * i <= n)
                    dp[i][j] = {min(a[b], a[2*i]), max(a[b], a[2*i])};
                else
                    dp[i][j] = {a[b]};
        }
        if(2 * i + 1 <= n)
            for(int j = 0; j <= 1; ++j)
                for(int k = 0; k <= 35; ++k)
                    if(v[2 * i + j][k])
                        vector<int>().swap(dp[2 * i + j][k]);
    }
    for(int i = 0; i < dp[1][0].size(); ++i)
        cout << dp[1][0][i] << " ";
    return 0;
}

Compilation message

swap.cpp: In function 'void mrg(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:24:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int stp=1, i=0, j=0; i<a.size() || j<b.size(); i+=stp, j+=stp, stp*=2)
                              ~^~~~~~~~~
swap.cpp:24:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int stp=1, i=0, j=0; i<a.size() || j<b.size(); i+=stp, j+=stp, stp*=2)
                                            ~^~~~~~~~~
swap.cpp:26:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int k = 0; k < stp && i+k < a.size(); ++k)
                                   ~~~~^~~~~~~~~~
swap.cpp:28:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int k = 0; k < stp && j+k < b.size(); ++k)
                                   ~~~~^~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:92:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < dp[1][0].size(); ++i)
                    ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 169464 KB Output is correct
2 Correct 108 ms 169464 KB Output is correct
3 Correct 101 ms 169464 KB Output is correct
4 Correct 101 ms 169464 KB Output is correct
5 Correct 104 ms 169468 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 169464 KB Output is correct
2 Correct 108 ms 169464 KB Output is correct
3 Correct 101 ms 169464 KB Output is correct
4 Correct 101 ms 169464 KB Output is correct
5 Correct 104 ms 169468 KB Output is correct
6 Correct 103 ms 169392 KB Output is correct
7 Correct 102 ms 169464 KB Output is correct
8 Correct 108 ms 169464 KB Output is correct
9 Correct 104 ms 169464 KB Output is correct
10 Correct 105 ms 169464 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 169464 KB Output is correct
2 Correct 108 ms 169464 KB Output is correct
3 Correct 101 ms 169464 KB Output is correct
4 Correct 101 ms 169464 KB Output is correct
5 Correct 104 ms 169468 KB Output is correct
6 Correct 103 ms 169392 KB Output is correct
7 Correct 102 ms 169464 KB Output is correct
8 Correct 108 ms 169464 KB Output is correct
9 Correct 104 ms 169464 KB Output is correct
10 Correct 105 ms 169464 KB Output is correct
11 Correct 100 ms 169544 KB Output is correct
12 Correct 103 ms 169596 KB Output is correct
13 Correct 104 ms 169592 KB Output is correct
14 Correct 105 ms 169720 KB Output is correct
15 Correct 109 ms 169720 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 169464 KB Output is correct
2 Correct 108 ms 169464 KB Output is correct
3 Correct 101 ms 169464 KB Output is correct
4 Correct 101 ms 169464 KB Output is correct
5 Correct 104 ms 169468 KB Output is correct
6 Correct 103 ms 169392 KB Output is correct
7 Correct 102 ms 169464 KB Output is correct
8 Correct 108 ms 169464 KB Output is correct
9 Correct 104 ms 169464 KB Output is correct
10 Correct 105 ms 169464 KB Output is correct
11 Correct 100 ms 169544 KB Output is correct
12 Correct 103 ms 169596 KB Output is correct
13 Correct 104 ms 169592 KB Output is correct
14 Correct 105 ms 169720 KB Output is correct
15 Correct 109 ms 169720 KB Output is correct
16 Correct 160 ms 173304 KB Output is correct
17 Correct 157 ms 173304 KB Output is correct
18 Correct 159 ms 173624 KB Output is correct
19 Correct 271 ms 183456 KB Output is correct
20 Correct 264 ms 183288 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 169464 KB Output is correct
2 Correct 108 ms 169464 KB Output is correct
3 Correct 101 ms 169464 KB Output is correct
4 Correct 101 ms 169464 KB Output is correct
5 Correct 104 ms 169468 KB Output is correct
6 Correct 103 ms 169392 KB Output is correct
7 Correct 102 ms 169464 KB Output is correct
8 Correct 108 ms 169464 KB Output is correct
9 Correct 104 ms 169464 KB Output is correct
10 Correct 105 ms 169464 KB Output is correct
11 Correct 100 ms 169544 KB Output is correct
12 Correct 103 ms 169596 KB Output is correct
13 Correct 104 ms 169592 KB Output is correct
14 Correct 105 ms 169720 KB Output is correct
15 Correct 109 ms 169720 KB Output is correct
16 Correct 160 ms 173304 KB Output is correct
17 Correct 157 ms 173304 KB Output is correct
18 Correct 159 ms 173624 KB Output is correct
19 Correct 271 ms 183456 KB Output is correct
20 Correct 264 ms 183288 KB Output is correct
21 Correct 347 ms 184952 KB Output is correct
22 Correct 366 ms 184824 KB Output is correct
23 Correct 362 ms 184952 KB Output is correct
24 Correct 883 ms 231288 KB Output is correct
25 Correct 863 ms 231288 KB Output is correct