oj.uz

Submission #1029677

# Submission time Handle Problem Language Result Execution time Memory
1029677 2024-07-21T08:05:12 Z MMihalev Swap (BOI16_swap) C++14
68 / 100
 593 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=5e5+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 11 ms 56920 KB Output is correct
2 Correct 12 ms 56924 KB Output is correct
3 Correct 14 ms 56920 KB Output is correct
4 Correct 12 ms 56920 KB Output is correct
5 Correct 13 ms 56960 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 56920 KB Output is correct
2 Correct 12 ms 56924 KB Output is correct
3 Correct 14 ms 56920 KB Output is correct
4 Correct 12 ms 56920 KB Output is correct
5 Correct 13 ms 56960 KB Output is correct
6 Correct 12 ms 57048 KB Output is correct
7 Correct 12 ms 56920 KB Output is correct
8 Correct 13 ms 56924 KB Output is correct
9 Correct 12 ms 56920 KB Output is correct
10 Correct 13 ms 56924 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 56920 KB Output is correct
2 Correct 12 ms 56924 KB Output is correct
3 Correct 14 ms 56920 KB Output is correct
4 Correct 12 ms 56920 KB Output is correct
5 Correct 13 ms 56960 KB Output is correct
6 Correct 12 ms 57048 KB Output is correct
7 Correct 12 ms 56920 KB Output is correct
8 Correct 13 ms 56924 KB Output is correct
9 Correct 12 ms 56920 KB Output is correct
10 Correct 13 ms 56924 KB Output is correct
11 Correct 13 ms 57432 KB Output is correct
12 Correct 14 ms 57436 KB Output is correct
13 Correct 13 ms 57480 KB Output is correct
14 Correct 15 ms 58136 KB Output is correct
15 Correct 16 ms 58204 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 56920 KB Output is correct
2 Correct 12 ms 56924 KB Output is correct
3 Correct 14 ms 56920 KB Output is correct
4 Correct 12 ms 56920 KB Output is correct
5 Correct 13 ms 56960 KB Output is correct
6 Correct 12 ms 57048 KB Output is correct
7 Correct 12 ms 56920 KB Output is correct
8 Correct 13 ms 56924 KB Output is correct
9 Correct 12 ms 56920 KB Output is correct
10 Correct 13 ms 56924 KB Output is correct
11 Correct 13 ms 57432 KB Output is correct
12 Correct 14 ms 57436 KB Output is correct
13 Correct 13 ms 57480 KB Output is correct
14 Correct 15 ms 58136 KB Output is correct
15 Correct 16 ms 58204 KB Output is correct
16 Correct 101 ms 86196 KB Output is correct
17 Correct 99 ms 85712 KB Output is correct
18 Correct 95 ms 86348 KB Output is correct
19 Correct 593 ms 174016 KB Output is correct
20 Correct 555 ms 172728 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 56920 KB Output is correct
2 Correct 12 ms 56924 KB Output is correct
3 Correct 14 ms 56920 KB Output is correct
4 Correct 12 ms 56920 KB Output is correct
5 Correct 13 ms 56960 KB Output is correct
6 Correct 12 ms 57048 KB Output is correct
7 Correct 12 ms 56920 KB Output is correct
8 Correct 13 ms 56924 KB Output is correct
9 Correct 12 ms 56920 KB Output is correct
10 Correct 13 ms 56924 KB Output is correct
11 Correct 13 ms 57432 KB Output is correct
12 Correct 14 ms 57436 KB Output is correct
13 Correct 13 ms 57480 KB Output is correct
14 Correct 15 ms 58136 KB Output is correct
15 Correct 16 ms 58204 KB Output is correct
16 Correct 101 ms 86196 KB Output is correct
17 Correct 99 ms 85712 KB Output is correct
18 Correct 95 ms 86348 KB Output is correct
19 Correct 593 ms 174016 KB Output is correct
20 Correct 555 ms 172728 KB Output is correct
21 Correct 454 ms 176988 KB Output is correct
22 Correct 439 ms 178268 KB Output is correct
23 Correct 509 ms 178440 KB Output is correct
24 Runtime error 496 ms 262144 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -