oj.uz

Submission #1030019

# Submission time Handle Problem Language Result Execution time Memory
1030019 2024-07-21T16:13:37 Z MMihalev Swap (BOI16_swap) C++14
68 / 100
 315 ms 262144 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 67 ms 170832 KB Output is correct
2 Correct 64 ms 170816 KB Output is correct
3 Correct 65 ms 170832 KB Output is correct
4 Correct 79 ms 171028 KB Output is correct
5 Correct 65 ms 170940 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 170832 KB Output is correct
2 Correct 64 ms 170816 KB Output is correct
3 Correct 65 ms 170832 KB Output is correct
4 Correct 79 ms 171028 KB Output is correct
5 Correct 65 ms 170940 KB Output is correct
6 Correct 74 ms 170828 KB Output is correct
7 Correct 62 ms 170832 KB Output is correct
8 Correct 75 ms 170836 KB Output is correct
9 Correct 73 ms 171088 KB Output is correct
10 Correct 71 ms 170816 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 170832 KB Output is correct
2 Correct 64 ms 170816 KB Output is correct
3 Correct 65 ms 170832 KB Output is correct
4 Correct 79 ms 171028 KB Output is correct
5 Correct 65 ms 170940 KB Output is correct
6 Correct 74 ms 170828 KB Output is correct
7 Correct 62 ms 170832 KB Output is correct
8 Correct 75 ms 170836 KB Output is correct
9 Correct 73 ms 171088 KB Output is correct
10 Correct 71 ms 170816 KB Output is correct
11 Correct 91 ms 171488 KB Output is correct
12 Correct 68 ms 171384 KB Output is correct
13 Correct 70 ms 171348 KB Output is correct
14 Correct 60 ms 171348 KB Output is correct
15 Correct 63 ms 171276 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 170832 KB Output is correct
2 Correct 64 ms 170816 KB Output is correct
3 Correct 65 ms 170832 KB Output is correct
4 Correct 79 ms 171028 KB Output is correct
5 Correct 65 ms 170940 KB Output is correct
6 Correct 74 ms 170828 KB Output is correct
7 Correct 62 ms 170832 KB Output is correct
8 Correct 75 ms 170836 KB Output is correct
9 Correct 73 ms 171088 KB Output is correct
10 Correct 71 ms 170816 KB Output is correct
11 Correct 91 ms 171488 KB Output is correct
12 Correct 68 ms 171384 KB Output is correct
13 Correct 70 ms 171348 KB Output is correct
14 Correct 60 ms 171348 KB Output is correct
15 Correct 63 ms 171276 KB Output is correct
16 Correct 305 ms 205772 KB Output is correct
17 Correct 277 ms 205708 KB Output is correct
18 Correct 315 ms 205904 KB Output is correct
19 Correct 253 ms 206424 KB Output is correct
20 Correct 209 ms 206352 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 170832 KB Output is correct
2 Correct 64 ms 170816 KB Output is correct
3 Correct 65 ms 170832 KB Output is correct
4 Correct 79 ms 171028 KB Output is correct
5 Correct 65 ms 170940 KB Output is correct
6 Correct 74 ms 170828 KB Output is correct
7 Correct 62 ms 170832 KB Output is correct
8 Correct 75 ms 170836 KB Output is correct
9 Correct 73 ms 171088 KB Output is correct
10 Correct 71 ms 170816 KB Output is correct
11 Correct 91 ms 171488 KB Output is correct
12 Correct 68 ms 171384 KB Output is correct
13 Correct 70 ms 171348 KB Output is correct
14 Correct 60 ms 171348 KB Output is correct
15 Correct 63 ms 171276 KB Output is correct
16 Correct 305 ms 205772 KB Output is correct
17 Correct 277 ms 205708 KB Output is correct
18 Correct 315 ms 205904 KB Output is correct
19 Correct 253 ms 206424 KB Output is correct
20 Correct 209 ms 206352 KB Output is correct
21 Runtime error 195 ms 262144 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -