oj.uz

Submission #1029872

# Submission time Handle Problem Language Result Execution time Memory
1029872 2024-07-21T13:02:48 Z MMihalev Swap (BOI16_swap) C++14
68 / 100
 636 ms 149272 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>
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")
using namespace std;
const int MAX_N=2e5+1;
map<int,vector<int>>dp[MAX_N];
map<int,bool>calc[MAX_N];
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;
    }
}
void rec(int u,int val)
{
    if(u>n)return;
    if(calc[u][val])return;

    int l=n+1,r=n+1,al=n+1,ar=n+1;
    if(2*u<=n){l=2*u;al=a[2*u];}
    if(2*u+1<=n){r=2*u+1;ar=a[2*u+1];}
    if(val<min(al,ar))
    {
        rec(l,al);
        rec(r,ar);

        dp[u][val].push_back(val);
        Merge(dp[u][val],dp[l][al],dp[r][ar]);
    }
    else if(al<min(val,ar))
    {
        rec(l,val);
        rec(r,ar);

        dp[u][val].push_back(al);
        Merge(dp[u][val],dp[l][val],dp[r][ar]);
    }
    else
    {
        vector<int>ans1,ans2;
        rec(l,al);rec(l,val);
        rec(r,al);rec(r,val);
        ans1.push_back(ar);ans2.push_back(ar);
        Merge(ans1,dp[l][al],dp[r][val]);
        Merge(ans2,dp[l][val],dp[r][al]);
        dp[u][val]=min(ans1,ans2);
    }
    calc[u][val]=1;
}
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];
    }
    rec(1,a[1]);
    for(int x:dp[1][a[1]])cout<<x<<" ";
    cout<<"\n";
    return 0;
}

Compilation message

swap.cpp:24:52: warning: bad option '-fbranch-target-load-optimize2' to pragma 'optimize' [-Wpragmas]
   24 | #pragma GCC optimize("branch-target-load-optimize2")
      |                                                    ^
swap.cpp:25:40: warning: bad option '-fbtr-bb-exclusive' to pragma 'optimize' [-Wpragmas]
   25 | #pragma GCC optimize("btr-bb-exclusive")
      |                                        ^
swap.cpp:32:65: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
   32 | void Merge(vector<int>& res,vector<int>& Left,vector<int>& Right)
      |                                                                 ^
swap.cpp:32:65: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
swap.cpp: In function 'void Merge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     while(idxL<Left.size() or idxR<Right.size())
      |           ~~~~^~~~~~~~~~~~
swap.cpp:37:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     while(idxL<Left.size() or idxR<Right.size())
      |                               ~~~~^~~~~~~~~~~~~
swap.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         while(idxL<Left.size() && cur--)res.push_back(Left[idxL++]);
      |               ~~~~^~~~~~~~~~~~
swap.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         while(idxR<Right.size() && cur--)res.push_back(Right[idxR++]);
      |               ~~~~^~~~~~~~~~~~~
swap.cpp: At global scope:
swap.cpp:46:23: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
   46 | void rec(int u,int val)
      |                       ^
swap.cpp:46:23: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
swap.cpp:82:14: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
   82 | signed main ()
      |              ^
swap.cpp:82:14: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19800 KB Output is correct
2 Correct 4 ms 19800 KB Output is correct
3 Correct 4 ms 19632 KB Output is correct
4 Correct 5 ms 19804 KB Output is correct
5 Correct 6 ms 19800 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19800 KB Output is correct
2 Correct 4 ms 19800 KB Output is correct
3 Correct 4 ms 19632 KB Output is correct
4 Correct 5 ms 19804 KB Output is correct
5 Correct 6 ms 19800 KB Output is correct
6 Correct 5 ms 19804 KB Output is correct
7 Correct 5 ms 19804 KB Output is correct
8 Correct 4 ms 19864 KB Output is correct
9 Correct 4 ms 19816 KB Output is correct
10 Correct 6 ms 19804 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19800 KB Output is correct
2 Correct 4 ms 19800 KB Output is correct
3 Correct 4 ms 19632 KB Output is correct
4 Correct 5 ms 19804 KB Output is correct
5 Correct 6 ms 19800 KB Output is correct
6 Correct 5 ms 19804 KB Output is correct
7 Correct 5 ms 19804 KB Output is correct
8 Correct 4 ms 19864 KB Output is correct
9 Correct 4 ms 19816 KB Output is correct
10 Correct 6 ms 19804 KB Output is correct
11 Correct 5 ms 20060 KB Output is correct
12 Correct 6 ms 20228 KB Output is correct
13 Correct 7 ms 20060 KB Output is correct
14 Correct 8 ms 21080 KB Output is correct
15 Correct 7 ms 21080 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19800 KB Output is correct
2 Correct 4 ms 19800 KB Output is correct
3 Correct 4 ms 19632 KB Output is correct
4 Correct 5 ms 19804 KB Output is correct
5 Correct 6 ms 19800 KB Output is correct
6 Correct 5 ms 19804 KB Output is correct
7 Correct 5 ms 19804 KB Output is correct
8 Correct 4 ms 19864 KB Output is correct
9 Correct 4 ms 19816 KB Output is correct
10 Correct 6 ms 19804 KB Output is correct
11 Correct 5 ms 20060 KB Output is correct
12 Correct 6 ms 20228 KB Output is correct
13 Correct 7 ms 20060 KB Output is correct
14 Correct 8 ms 21080 KB Output is correct
15 Correct 7 ms 21080 KB Output is correct
16 Correct 96 ms 43732 KB Output is correct
17 Correct 85 ms 43472 KB Output is correct
18 Correct 95 ms 44016 KB Output is correct
19 Correct 636 ms 149272 KB Output is correct
20 Correct 633 ms 148100 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19800 KB Output is correct
2 Correct 4 ms 19800 KB Output is correct
3 Correct 4 ms 19632 KB Output is correct
4 Correct 5 ms 19804 KB Output is correct
5 Correct 6 ms 19800 KB Output is correct
6 Correct 5 ms 19804 KB Output is correct
7 Correct 5 ms 19804 KB Output is correct
8 Correct 4 ms 19864 KB Output is correct
9 Correct 4 ms 19816 KB Output is correct
10 Correct 6 ms 19804 KB Output is correct
11 Correct 5 ms 20060 KB Output is correct
12 Correct 6 ms 20228 KB Output is correct
13 Correct 7 ms 20060 KB Output is correct
14 Correct 8 ms 21080 KB Output is correct
15 Correct 7 ms 21080 KB Output is correct
16 Correct 96 ms 43732 KB Output is correct
17 Correct 85 ms 43472 KB Output is correct
18 Correct 95 ms 44016 KB Output is correct
19 Correct 636 ms 149272 KB Output is correct
20 Correct 633 ms 148100 KB Output is correct
21 Runtime error 40 ms 41488 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -