oj.uz

Submission #1030014

# Submission time Handle Problem Language Result Execution time Memory
1030014 2024-07-21T16:08:12 Z MMihalev Swap (BOI16_swap) C++14
100 / 100
 651 ms 254564 KB 
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<tuple>
#include<set>
#include<map>
#include<random>
#include<chrono>
#include<array>
#include<unordered_map>
using namespace std;
const int MAX_N=2e5+5;
const int LOG=18;
vector<int>dp[MAX_N][LOG][2],tmp1,tmp2;
bool need[MAX_N][LOG][2];
int a[MAX_N];
int n;
void Merge(vector<int>& res,vector<int>& Left,vector<int>& Right)
{
    int nums=1;
    int idxL=0;
    int idxR=0;
    while(idxL<Left.size() or idxR<Right.size())
    {
        int cur=nums;
        while(idxL<Left.size() && cur--)res.push_back(Left[idxL++]);
        cur=nums;
        while(idxR<Right.size() && cur--)res.push_back(Right[idxR++]);
        nums*=2;
    }
}
signed main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    a[n+1]=1e9;

    need[1][0][1]=1;
    for(int node=1;node<=n/2;node++)
    {
        for(int i=0;node>>i;i++)
        {
            for(int j:{0,1})
            {
                if(!need[node][i][j])continue;

                int idx=((node>>i+1)<<1)+j;
                int mn=min(a[2*node+1],min(a[idx],a[2*node]));
                if(a[idx]==mn)
                {
                    need[2*node][0][0]=1;
                    need[2*node+1][0][1]=1;
                }
                else if(a[2*node]==mn)
                {
                    need[2*node][i+1][j]=1;
                    need[2*node+1][0][1]=1;
                }
                else
                {
                    need[2*node][i+1][j]=1;
                    need[2*node+1][0][0]=1;

                    need[2*node][0][0]=1;
                    need[2*node+1][i+1][j]=1;
                }
            }
        }
    }


    for(int node=n;node>=1;node--)
    {
        for(int i=0;node>>i;i++)
        {
            for(int j:{0,1})
            {
                if(!need[node][i][j])continue;

                int idx=((node>>i+1)<<1)+j;

                if(2*node>n)
                {
                    dp[node][i][j].push_back(a[idx]);
                }
                else if(2*node==n)
                {
                    dp[node][i][j].push_back(min(a[idx],a[2*node]));
                    dp[node][i][j].push_back(max(a[idx],a[2*node]));
                }
                else
                {
                    if(a[idx]<min(a[2*node],a[2*node+1]))
                    {
                        dp[node][i][j].push_back(a[idx]);
                        Merge(dp[node][i][j],dp[2*node][0][0],dp[2*node+1][0][1]);
                    }
                    else if(a[2*node]<min(a[idx],a[2*node+1]))
                    {
                        dp[node][i][j].push_back(a[2*node]);
                        Merge(dp[node][i][j],dp[2*node][i+1][j],dp[2*node+1][0][1]);
                    }
                    else
                    {
                        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);
                    }
                }
            }
        }
        if(2*node<n)
        {
            for(int i=0;node>>i;i++)
            {
                for(int j:{0,1})
                {
                    vector<int>().swap(dp[2*node][i][j]);
                    vector<int>().swap(dp[2*node+1][i][j]);
                }
            }
        }
    }

    for(int x:dp[1][0][1])cout<<x<<" ";
    cout<<"\n";

    return 0;
}

Compilation message

swap.cpp: In function 'void Merge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     while(idxL<Left.size() or idxR<Right.size())
      |           ~~~~^~~~~~~~~~~~
swap.cpp:28:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     while(idxL<Left.size() or idxR<Right.size())
      |                               ~~~~^~~~~~~~~~~~~
swap.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         while(idxL<Left.size() && cur--)res.push_back(Left[idxL++]);
      |               ~~~~^~~~~~~~~~~~
swap.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         while(idxR<Right.size() && cur--)res.push_back(Right[idxR++]);
      |               ~~~~^~~~~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:59:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |                 int idx=((node>>i+1)<<1)+j;
      |                                 ~^~
swap.cpp:92:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |                 int idx=((node>>i+1)<<1)+j;
      |                                 ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 170832 KB Output is correct
2 Correct 66 ms 170836 KB Output is correct
3 Correct 80 ms 170836 KB Output is correct
4 Correct 74 ms 170840 KB Output is correct
5 Correct 67 ms 170928 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 170832 KB Output is correct
2 Correct 66 ms 170836 KB Output is correct
3 Correct 80 ms 170836 KB Output is correct
4 Correct 74 ms 170840 KB Output is correct
5 Correct 67 ms 170928 KB Output is correct
6 Correct 68 ms 171036 KB Output is correct
7 Correct 61 ms 170832 KB Output is correct
8 Correct 69 ms 170832 KB Output is correct
9 Correct 80 ms 170832 KB Output is correct
10 Correct 67 ms 170832 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 170832 KB Output is correct
2 Correct 66 ms 170836 KB Output is correct
3 Correct 80 ms 170836 KB Output is correct
4 Correct 74 ms 170840 KB Output is correct
5 Correct 67 ms 170928 KB Output is correct
6 Correct 68 ms 171036 KB Output is correct
7 Correct 61 ms 170832 KB Output is correct
8 Correct 69 ms 170832 KB Output is correct
9 Correct 80 ms 170832 KB Output is correct
10 Correct 67 ms 170832 KB Output is correct
11 Correct 79 ms 171092 KB Output is correct
12 Correct 79 ms 171056 KB Output is correct
13 Correct 77 ms 171072 KB Output is correct
14 Correct 78 ms 171344 KB Output is correct
15 Correct 75 ms 171260 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 170832 KB Output is correct
2 Correct 66 ms 170836 KB Output is correct
3 Correct 80 ms 170836 KB Output is correct
4 Correct 74 ms 170840 KB Output is correct
5 Correct 67 ms 170928 KB Output is correct
6 Correct 68 ms 171036 KB Output is correct
7 Correct 61 ms 170832 KB Output is correct
8 Correct 69 ms 170832 KB Output is correct
9 Correct 80 ms 170832 KB Output is correct
10 Correct 67 ms 170832 KB Output is correct
11 Correct 79 ms 171092 KB Output is correct
12 Correct 79 ms 171056 KB Output is correct
13 Correct 77 ms 171072 KB Output is correct
14 Correct 78 ms 171344 KB Output is correct
15 Correct 75 ms 171260 KB Output is correct
16 Correct 123 ms 175568 KB Output is correct
17 Correct 98 ms 175264 KB Output is correct
18 Correct 112 ms 175980 KB Output is correct
19 Correct 149 ms 190672 KB Output is correct
20 Correct 167 ms 190352 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 170832 KB Output is correct
2 Correct 66 ms 170836 KB Output is correct
3 Correct 80 ms 170836 KB Output is correct
4 Correct 74 ms 170840 KB Output is correct
5 Correct 67 ms 170928 KB Output is correct
6 Correct 68 ms 171036 KB Output is correct
7 Correct 61 ms 170832 KB Output is correct
8 Correct 69 ms 170832 KB Output is correct
9 Correct 80 ms 170832 KB Output is correct
10 Correct 67 ms 170832 KB Output is correct
11 Correct 79 ms 171092 KB Output is correct
12 Correct 79 ms 171056 KB Output is correct
13 Correct 77 ms 171072 KB Output is correct
14 Correct 78 ms 171344 KB Output is correct
15 Correct 75 ms 171260 KB Output is correct
16 Correct 123 ms 175568 KB Output is correct
17 Correct 98 ms 175264 KB Output is correct
18 Correct 112 ms 175980 KB Output is correct
19 Correct 149 ms 190672 KB Output is correct
20 Correct 167 ms 190352 KB Output is correct
21 Correct 269 ms 187056 KB Output is correct
22 Correct 305 ms 188196 KB Output is correct
23 Correct 282 ms 188104 KB Output is correct
24 Correct 617 ms 254252 KB Output is correct
25 Correct 651 ms 254564 KB Output is correct