oj.uz

Submission #1029876

# Submission time Handle Problem Language Result Execution time Memory
1029876 2024-07-21T13:05:04 Z MMihalev Swap (BOI16_swap) C++14
68 / 100
 675 ms 148528 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+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: In function 'void Merge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     while(idxL<Left.size() or idxR<Right.size())
      |           ~~~~^~~~~~~~~~~~
swap.cpp:27:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     while(idxL<Left.size() or idxR<Right.size())
      |                               ~~~~^~~~~~~~~~~~~
swap.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         while(idxL<Left.size() && cur--)res.push_back(Left[idxL++]);
      |               ~~~~^~~~~~~~~~~~
swap.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         while(idxR<Right.size() && cur--)res.push_back(Right[idxR++]);
      |               ~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19032 KB Output is correct
2 Correct 9 ms 19036 KB Output is correct
3 Correct 8 ms 19096 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 9 ms 19032 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19032 KB Output is correct
2 Correct 9 ms 19036 KB Output is correct
3 Correct 8 ms 19096 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 9 ms 19032 KB Output is correct
6 Correct 9 ms 19148 KB Output is correct
7 Correct 9 ms 19176 KB Output is correct
8 Correct 8 ms 19036 KB Output is correct
9 Correct 9 ms 19036 KB Output is correct
10 Correct 8 ms 19220 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19032 KB Output is correct
2 Correct 9 ms 19036 KB Output is correct
3 Correct 8 ms 19096 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 9 ms 19032 KB Output is correct
6 Correct 9 ms 19148 KB Output is correct
7 Correct 9 ms 19176 KB Output is correct
8 Correct 8 ms 19036 KB Output is correct
9 Correct 9 ms 19036 KB Output is correct
10 Correct 8 ms 19220 KB Output is correct
11 Correct 9 ms 19548 KB Output is correct
12 Correct 12 ms 19640 KB Output is correct
13 Correct 10 ms 19548 KB Output is correct
14 Correct 13 ms 20548 KB Output is correct
15 Correct 13 ms 20572 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19032 KB Output is correct
2 Correct 9 ms 19036 KB Output is correct
3 Correct 8 ms 19096 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 9 ms 19032 KB Output is correct
6 Correct 9 ms 19148 KB Output is correct
7 Correct 9 ms 19176 KB Output is correct
8 Correct 8 ms 19036 KB Output is correct
9 Correct 9 ms 19036 KB Output is correct
10 Correct 8 ms 19220 KB Output is correct
11 Correct 9 ms 19548 KB Output is correct
12 Correct 12 ms 19640 KB Output is correct
13 Correct 10 ms 19548 KB Output is correct
14 Correct 13 ms 20548 KB Output is correct
15 Correct 13 ms 20572 KB Output is correct
16 Correct 88 ms 42740 KB Output is correct
17 Correct 97 ms 42704 KB Output is correct
18 Correct 93 ms 43084 KB Output is correct
19 Correct 675 ms 148528 KB Output is correct
20 Correct 598 ms 147428 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19032 KB Output is correct
2 Correct 9 ms 19036 KB Output is correct
3 Correct 8 ms 19096 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 9 ms 19032 KB Output is correct
6 Correct 9 ms 19148 KB Output is correct
7 Correct 9 ms 19176 KB Output is correct
8 Correct 8 ms 19036 KB Output is correct
9 Correct 9 ms 19036 KB Output is correct
10 Correct 8 ms 19220 KB Output is correct
11 Correct 9 ms 19548 KB Output is correct
12 Correct 12 ms 19640 KB Output is correct
13 Correct 10 ms 19548 KB Output is correct
14 Correct 13 ms 20548 KB Output is correct
15 Correct 13 ms 20572 KB Output is correct
16 Correct 88 ms 42740 KB Output is correct
17 Correct 97 ms 42704 KB Output is correct
18 Correct 93 ms 43084 KB Output is correct
19 Correct 675 ms 148528 KB Output is correct
20 Correct 598 ms 147428 KB Output is correct
21 Runtime error 46 ms 40044 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -