oj.uz

답안 #1029690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1029690 2024-07-21T08:12:49 Z MMihalev Swap (BOI16_swap) C++14
68 / 100
 540 ms 149080 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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19804 KB Output is correct
2 Correct 4 ms 19804 KB Output is correct
3 Correct 3 ms 19804 KB Output is correct
4 Correct 3 ms 19804 KB Output is correct
5 Correct 3 ms 19804 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19804 KB Output is correct
2 Correct 4 ms 19804 KB Output is correct
3 Correct 3 ms 19804 KB Output is correct
4 Correct 3 ms 19804 KB Output is correct
5 Correct 3 ms 19804 KB Output is correct
6 Correct 3 ms 19804 KB Output is correct
7 Correct 3 ms 19804 KB Output is correct
8 Correct 3 ms 19804 KB Output is correct
9 Correct 3 ms 19804 KB Output is correct
10 Correct 3 ms 19804 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19804 KB Output is correct
2 Correct 4 ms 19804 KB Output is correct
3 Correct 3 ms 19804 KB Output is correct
4 Correct 3 ms 19804 KB Output is correct
5 Correct 3 ms 19804 KB Output is correct
6 Correct 3 ms 19804 KB Output is correct
7 Correct 3 ms 19804 KB Output is correct
8 Correct 3 ms 19804 KB Output is correct
9 Correct 3 ms 19804 KB Output is correct
10 Correct 3 ms 19804 KB Output is correct
11 Correct 4 ms 20056 KB Output is correct
12 Correct 4 ms 20316 KB Output is correct
13 Correct 4 ms 20056 KB Output is correct
14 Correct 7 ms 21112 KB Output is correct
15 Correct 6 ms 21084 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19804 KB Output is correct
2 Correct 4 ms 19804 KB Output is correct
3 Correct 3 ms 19804 KB Output is correct
4 Correct 3 ms 19804 KB Output is correct
5 Correct 3 ms 19804 KB Output is correct
6 Correct 3 ms 19804 KB Output is correct
7 Correct 3 ms 19804 KB Output is correct
8 Correct 3 ms 19804 KB Output is correct
9 Correct 3 ms 19804 KB Output is correct
10 Correct 3 ms 19804 KB Output is correct
11 Correct 4 ms 20056 KB Output is correct
12 Correct 4 ms 20316 KB Output is correct
13 Correct 4 ms 20056 KB Output is correct
14 Correct 7 ms 21112 KB Output is correct
15 Correct 6 ms 21084 KB Output is correct
16 Correct 62 ms 43412 KB Output is correct
17 Correct 71 ms 43216 KB Output is correct
18 Correct 78 ms 43852 KB Output is correct
19 Correct 498 ms 149080 KB Output is correct
20 Correct 540 ms 147856 KB Output is correct

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 19804 KB Output is correct
2 Correct 4 ms 19804 KB Output is correct
3 Correct 3 ms 19804 KB Output is correct
4 Correct 3 ms 19804 KB Output is correct
5 Correct 3 ms 19804 KB Output is correct
6 Correct 3 ms 19804 KB Output is correct
7 Correct 3 ms 19804 KB Output is correct
8 Correct 3 ms 19804 KB Output is correct
9 Correct 3 ms 19804 KB Output is correct
10 Correct 3 ms 19804 KB Output is correct
11 Correct 4 ms 20056 KB Output is correct
12 Correct 4 ms 20316 KB Output is correct
13 Correct 4 ms 20056 KB Output is correct
14 Correct 7 ms 21112 KB Output is correct
15 Correct 6 ms 21084 KB Output is correct
16 Correct 62 ms 43412 KB Output is correct
17 Correct 71 ms 43216 KB Output is correct
18 Correct 78 ms 43852 KB Output is correct
19 Correct 498 ms 149080 KB Output is correct
20 Correct 540 ms 147856 KB Output is correct
21 Runtime error 26 ms 40284 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -