oj.uz

Submission #1029676

# Submission time Handle Problem Language Result Execution time Memory
1029676 2024-07-21T08:04:28 Z MMihalev Swap (BOI16_swap) C++14
68 / 100
 570 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=4e5+2;
unordered_map<int,vector<int>>dp[MAX_N];
unordered_map<int,bool>calc[MAX_N];
int a[MAX_N];
int n;
vector<int> Merge(int u,vector<int>& Left,vector<int>& Right)
{
    vector<int>res;
    res.push_back(u);
    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;
    }
    return res;
}
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]=Merge(val,dp[l][al],dp[r][ar]);
    }
    else if(al<min(val,ar))
    {
        rec(l,val);
        rec(r,ar);
        dp[u][val]=Merge(al,dp[l][val],dp[r][ar]);
    }
    else
    {
        rec(l,al);rec(l,val);
        rec(r,al);rec(r,val);
        dp[u][val]=min(Merge(ar,dp[l][al],dp[r][val]),
                       Merge(ar,dp[l][val],dp[r][al]));
    }
    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 'std::vector<int> Merge(int, std::vector<int>&, std::vector<int>&)':
swap.cpp:29:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while(idxL<Left.size() or idxR<Right.size())
      |           ~~~~^~~~~~~~~~~~
swap.cpp:29:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while(idxL<Left.size() or idxR<Right.size())
      |                               ~~~~^~~~~~~~~~~~~
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(idxL<Left.size() && cur--)res.push_back(Left[idxL++]);
      |               ~~~~^~~~~~~~~~~~
swap.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         while(idxR<Right.size() && cur--)res.push_back(Right[idxR++]);
      |               ~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 45656 KB Output is correct
2 Correct 9 ms 45660 KB Output is correct
3 Correct 9 ms 45688 KB Output is correct
4 Correct 9 ms 45656 KB Output is correct
5 Correct 10 ms 45660 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 45656 KB Output is correct
2 Correct 9 ms 45660 KB Output is correct
3 Correct 9 ms 45688 KB Output is correct
4 Correct 9 ms 45656 KB Output is correct
5 Correct 10 ms 45660 KB Output is correct
6 Correct 9 ms 45660 KB Output is correct
7 Correct 8 ms 45660 KB Output is correct
8 Correct 8 ms 45516 KB Output is correct
9 Correct 8 ms 45660 KB Output is correct
10 Correct 8 ms 45660 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 45656 KB Output is correct
2 Correct 9 ms 45660 KB Output is correct
3 Correct 9 ms 45688 KB Output is correct
4 Correct 9 ms 45656 KB Output is correct
5 Correct 10 ms 45660 KB Output is correct
6 Correct 9 ms 45660 KB Output is correct
7 Correct 8 ms 45660 KB Output is correct
8 Correct 8 ms 45516 KB Output is correct
9 Correct 8 ms 45660 KB Output is correct
10 Correct 8 ms 45660 KB Output is correct
11 Correct 10 ms 46168 KB Output is correct
12 Correct 10 ms 46172 KB Output is correct
13 Correct 10 ms 46172 KB Output is correct
14 Correct 12 ms 46680 KB Output is correct
15 Correct 15 ms 46684 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 45656 KB Output is correct
2 Correct 9 ms 45660 KB Output is correct
3 Correct 9 ms 45688 KB Output is correct
4 Correct 9 ms 45656 KB Output is correct
5 Correct 10 ms 45660 KB Output is correct
6 Correct 9 ms 45660 KB Output is correct
7 Correct 8 ms 45660 KB Output is correct
8 Correct 8 ms 45516 KB Output is correct
9 Correct 8 ms 45660 KB Output is correct
10 Correct 8 ms 45660 KB Output is correct
11 Correct 10 ms 46168 KB Output is correct
12 Correct 10 ms 46172 KB Output is correct
13 Correct 10 ms 46172 KB Output is correct
14 Correct 12 ms 46680 KB Output is correct
15 Correct 15 ms 46684 KB Output is correct
16 Correct 87 ms 74664 KB Output is correct
17 Correct 88 ms 74540 KB Output is correct
18 Correct 113 ms 74796 KB Output is correct
19 Correct 545 ms 162612 KB Output is correct
20 Correct 565 ms 161468 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 45656 KB Output is correct
2 Correct 9 ms 45660 KB Output is correct
3 Correct 9 ms 45688 KB Output is correct
4 Correct 9 ms 45656 KB Output is correct
5 Correct 10 ms 45660 KB Output is correct
6 Correct 9 ms 45660 KB Output is correct
7 Correct 8 ms 45660 KB Output is correct
8 Correct 8 ms 45516 KB Output is correct
9 Correct 8 ms 45660 KB Output is correct
10 Correct 8 ms 45660 KB Output is correct
11 Correct 10 ms 46168 KB Output is correct
12 Correct 10 ms 46172 KB Output is correct
13 Correct 10 ms 46172 KB Output is correct
14 Correct 12 ms 46680 KB Output is correct
15 Correct 15 ms 46684 KB Output is correct
16 Correct 87 ms 74664 KB Output is correct
17 Correct 88 ms 74540 KB Output is correct
18 Correct 113 ms 74796 KB Output is correct
19 Correct 545 ms 162612 KB Output is correct
20 Correct 565 ms 161468 KB Output is correct
21 Correct 522 ms 165868 KB Output is correct
22 Correct 479 ms 166712 KB Output is correct
23 Correct 443 ms 167176 KB Output is correct
24 Runtime error 570 ms 262144 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -