oj.uz

답안 #1030012

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1030012 2024-07-21T16:04:56 Z MMihalev Swap (BOI16_swap) C++14
68 / 100
 278 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);
                    }
                }
            }
        }
    }

    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

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 170936 KB Output is correct
2 Correct 67 ms 170952 KB Output is correct
3 Correct 71 ms 171028 KB Output is correct
4 Correct 76 ms 170940 KB Output is correct
5 Correct 60 ms 171020 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 170936 KB Output is correct
2 Correct 67 ms 170952 KB Output is correct
3 Correct 71 ms 171028 KB Output is correct
4 Correct 76 ms 170940 KB Output is correct
5 Correct 60 ms 171020 KB Output is correct
6 Correct 63 ms 170828 KB Output is correct
7 Correct 63 ms 170792 KB Output is correct
8 Correct 66 ms 170896 KB Output is correct
9 Correct 60 ms 170832 KB Output is correct
10 Correct 69 ms 170836 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 170936 KB Output is correct
2 Correct 67 ms 170952 KB Output is correct
3 Correct 71 ms 171028 KB Output is correct
4 Correct 76 ms 170940 KB Output is correct
5 Correct 60 ms 171020 KB Output is correct
6 Correct 63 ms 170828 KB Output is correct
7 Correct 63 ms 170792 KB Output is correct
8 Correct 66 ms 170896 KB Output is correct
9 Correct 60 ms 170832 KB Output is correct
10 Correct 69 ms 170836 KB Output is correct
11 Correct 69 ms 171020 KB Output is correct
12 Correct 59 ms 171088 KB Output is correct
13 Correct 57 ms 171116 KB Output is correct
14 Correct 67 ms 171348 KB Output is correct
15 Correct 57 ms 171348 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 170936 KB Output is correct
2 Correct 67 ms 170952 KB Output is correct
3 Correct 71 ms 171028 KB Output is correct
4 Correct 76 ms 170940 KB Output is correct
5 Correct 60 ms 171020 KB Output is correct
6 Correct 63 ms 170828 KB Output is correct
7 Correct 63 ms 170792 KB Output is correct
8 Correct 66 ms 170896 KB Output is correct
9 Correct 60 ms 170832 KB Output is correct
10 Correct 69 ms 170836 KB Output is correct
11 Correct 69 ms 171020 KB Output is correct
12 Correct 59 ms 171088 KB Output is correct
13 Correct 57 ms 171116 KB Output is correct
14 Correct 67 ms 171348 KB Output is correct
15 Correct 57 ms 171348 KB Output is correct
16 Correct 115 ms 182032 KB Output is correct
17 Correct 103 ms 181708 KB Output is correct
18 Correct 92 ms 182224 KB Output is correct
19 Correct 171 ms 213292 KB Output is correct
20 Correct 148 ms 212808 KB Output is correct

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 170936 KB Output is correct
2 Correct 67 ms 170952 KB Output is correct
3 Correct 71 ms 171028 KB Output is correct
4 Correct 76 ms 170940 KB Output is correct
5 Correct 60 ms 171020 KB Output is correct
6 Correct 63 ms 170828 KB Output is correct
7 Correct 63 ms 170792 KB Output is correct
8 Correct 66 ms 170896 KB Output is correct
9 Correct 60 ms 170832 KB Output is correct
10 Correct 69 ms 170836 KB Output is correct
11 Correct 69 ms 171020 KB Output is correct
12 Correct 59 ms 171088 KB Output is correct
13 Correct 57 ms 171116 KB Output is correct
14 Correct 67 ms 171348 KB Output is correct
15 Correct 57 ms 171348 KB Output is correct
16 Correct 115 ms 182032 KB Output is correct
17 Correct 103 ms 181708 KB Output is correct
18 Correct 92 ms 182224 KB Output is correct
19 Correct 171 ms 213292 KB Output is correct
20 Correct 148 ms 212808 KB Output is correct
21 Correct 272 ms 217140 KB Output is correct
22 Correct 258 ms 217748 KB Output is correct
23 Correct 278 ms 218228 KB Output is correct
24 Runtime error 249 ms 262144 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -