oj.uz

Submission #937749

# Submission time Handle Problem Language Result Execution time Memory
937749 2024-03-04T12:34:42 Z 1075508020060209tc Swap (BOI16_swap) C++14
48 / 100
 41 ms 49872 KB 
#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
int n;
int ar[200005];
vector<int>dp[1010][1010];

void chmn(vector<int>&nw,vector<int>a,vector<int>b){
/*
cout<<a.size()<<" "<<b.size()<<"hehe\n";
for(int v:a){
    cout<<v<<" ";
}    cout<<endl;
for(int v:b){
    cout<<v<<" ";
}cout<<endl;*/

for(int i=0;i<min(a.size(),b.size());i++){
    if(a[i]<b[i]){
        swap(nw,a);
        return;
    }
    if(a[i]>b[i]){
        swap(nw,b);
        return;
    }
}
if(a.size()<b.size()){
    swap(nw,a);
    return;
}
swap(nw,b);
}

void mrg(vector<int>&vc,vector<int>&a,vector<int>&b){
int ait=0;int bit=0;
for(int lg=0;(1<<lg)<=a.size()*2;lg++){
    for(int k=0;k<(1<<lg)&&(ait+k)<a.size();k++){
        vc.push_back(a[ait+k]);
    }
    ait+=(1<<lg);
    for(int k=0;k<(1<<lg)&&(bit+k)<b.size();k++){
        vc.push_back(b[bit+k]);
    }
    bit+=(1<<lg);
}
}


void solve(int nw,int nwv){
if(dp[nw][nwv].size()){return;}
if(nw*2>n){
    dp[nw][nwv]={nwv};
    return;
}
if(nw*2+1>n){
    chmn(dp[nw][nwv],{nwv,ar[nw*2]},{ar[nw*2],nwv});
    return;
}
if(nwv<ar[nw*2]&&nwv<ar[nw*2+1]){
    dp[nw][nwv].push_back(nwv);
    solve(nw*2,ar[nw*2]);
    solve(nw*2+1,ar[nw*2+1]);
    mrg(dp[nw][nwv],dp[nw*2][ar[nw*2]],dp[nw*2+1][ar[nw*2+1]]);
    return;
}

if(ar[nw*2]<nwv&&ar[nw*2]<ar[nw*2+1]){
    dp[nw][nwv].push_back(ar[nw*2]);
    solve(nw*2,nwv);
    solve(nw*2+1,ar[nw*2+1]);
    mrg(dp[nw][nwv],dp[nw*2][nwv],dp[nw*2+1][ar[nw*2+1]]);
    return;
}
//cout<<"aa";
vector<int>vc;
vc.push_back(ar[nw*2+1]);
solve(nw*2,nwv);
solve(nw*2+1,ar[nw*2]);
mrg(vc,dp[nw*2][nwv],dp[nw*2+1][ar[nw*2]]);
dp[nw][nwv].push_back(ar[nw*2+1]);
solve(nw*2,ar[nw*2]);
solve(nw*2+1,nwv);
mrg(dp[nw][nwv],dp[nw*2][ar[nw*2]],dp[nw*2+1][nwv]);
chmn(dp[nw][nwv],dp[nw][nwv],vc);
}



signed main(){
cin>>n;
for(int i=1;i<=n;i++){
    cin>>ar[i];
}
solve(1,ar[1]);
for(int i=0;i<dp[1][ar[1]].size();i++){
    cout<<dp[1][ar[1]][i]<<" ";
}cout<<endl;
return 0;
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(dp[i][j].size()){
            cout<<i<<" "<<j<<":";
            for(int v:dp[i][j]){
                cout<<v<<" ";
            }
            cout<<endl;
        }
    }
}



}

Compilation message

swap.cpp: In function 'void chmn(std::vector<int>&, std::vector<int>, std::vector<int>)':
swap.cpp:18:14: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   18 | for(int i=0;i<min(a.size(),b.size());i++){
      |             ~^~~~~~~~~~~~~~~~~~~~~~~
swap.cpp: In function 'void mrg(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 | for(int lg=0;(1<<lg)<=a.size()*2;lg++){
      |              ~~~~~~~^~~~~~~~~~~~
swap.cpp:38:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int k=0;k<(1<<lg)&&(ait+k)<a.size();k++){
      |                            ~~~~~~~^~~~~~~~~
swap.cpp:42:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int k=0;k<(1<<lg)&&(bit+k)<b.size();k++){
      |                            ~~~~~~~^~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:96:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 | for(int i=0;i<dp[1][ar[1]].size();i++){
      |             ~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24156 KB Output is correct
2 Correct 8 ms 24156 KB Output is correct
3 Correct 5 ms 24156 KB Output is correct
4 Correct 6 ms 24156 KB Output is correct
5 Correct 6 ms 24156 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24156 KB Output is correct
2 Correct 8 ms 24156 KB Output is correct
3 Correct 5 ms 24156 KB Output is correct
4 Correct 6 ms 24156 KB Output is correct
5 Correct 6 ms 24156 KB Output is correct
6 Correct 7 ms 24156 KB Output is correct
7 Correct 6 ms 24156 KB Output is correct
8 Correct 6 ms 24396 KB Output is correct
9 Correct 6 ms 24156 KB Output is correct
10 Correct 6 ms 24156 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24156 KB Output is correct
2 Correct 8 ms 24156 KB Output is correct
3 Correct 5 ms 24156 KB Output is correct
4 Correct 6 ms 24156 KB Output is correct
5 Correct 6 ms 24156 KB Output is correct
6 Correct 7 ms 24156 KB Output is correct
7 Correct 6 ms 24156 KB Output is correct
8 Correct 6 ms 24396 KB Output is correct
9 Correct 6 ms 24156 KB Output is correct
10 Correct 6 ms 24156 KB Output is correct
11 Correct 7 ms 24412 KB Output is correct
12 Correct 7 ms 24412 KB Output is correct
13 Correct 7 ms 24412 KB Output is correct
14 Correct 9 ms 24668 KB Output is correct
15 Correct 10 ms 24692 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24156 KB Output is correct
2 Correct 8 ms 24156 KB Output is correct
3 Correct 5 ms 24156 KB Output is correct
4 Correct 6 ms 24156 KB Output is correct
5 Correct 6 ms 24156 KB Output is correct
6 Correct 7 ms 24156 KB Output is correct
7 Correct 6 ms 24156 KB Output is correct
8 Correct 6 ms 24396 KB Output is correct
9 Correct 6 ms 24156 KB Output is correct
10 Correct 6 ms 24156 KB Output is correct
11 Correct 7 ms 24412 KB Output is correct
12 Correct 7 ms 24412 KB Output is correct
13 Correct 7 ms 24412 KB Output is correct
14 Correct 9 ms 24668 KB Output is correct
15 Correct 10 ms 24692 KB Output is correct
16 Runtime error 41 ms 49872 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24156 KB Output is correct
2 Correct 8 ms 24156 KB Output is correct
3 Correct 5 ms 24156 KB Output is correct
4 Correct 6 ms 24156 KB Output is correct
5 Correct 6 ms 24156 KB Output is correct
6 Correct 7 ms 24156 KB Output is correct
7 Correct 6 ms 24156 KB Output is correct
8 Correct 6 ms 24396 KB Output is correct
9 Correct 6 ms 24156 KB Output is correct
10 Correct 6 ms 24156 KB Output is correct
11 Correct 7 ms 24412 KB Output is correct
12 Correct 7 ms 24412 KB Output is correct
13 Correct 7 ms 24412 KB Output is correct
14 Correct 9 ms 24668 KB Output is correct
15 Correct 10 ms 24692 KB Output is correct
16 Runtime error 41 ms 49872 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -