제출 #937772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937772		1075508020060209tc	Swap (BOI16_swap)	C++14	68 / 100	533 ms	262144 KiB

swap

#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
int n;
int ar[200005];
map<int,vector<int>>dp[200005];
void chmn(vector<int>&nw,vector<int>a,vector<int>b){

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);
}
}

vector<pair<int,int>>seq;
map<int,int>vis[200005];

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

if(ar[nw*2]<nwv&&ar[nw*2]<ar[nw*2+1]){
    dfs(nw*2,nwv);
    dfs(nw*2+1,ar[nw*2+1]);
    seq.push_back({nw,nwv});
    return;
}

dfs(nw*2,nwv);
dfs(nw*2+1,ar[nw*2]);

dfs(nw*2,ar[nw*2]);
dfs(nw*2+1,nwv);
seq.push_back({nw,nwv});

}


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;
}
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.tie(0);
ios_base::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;i++){
    cin>>ar[i];
}

dfs(1,ar[1]);

for(int i=0;i<seq.size();i++){
    solve(seq[i].first,seq[i].second);
}
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;
        }
    }
}



}

컴파일 시 표준 에러 (stderr) 메시지

swap.cpp: In function 'void chmn(std::vector<int>&, std::vector<int>, std::vector<int>)':
swap.cpp:9:14: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
    9 | 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:28:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 | for(int lg=0;(1<<lg)<=a.size()*2;lg++){
      |              ~~~~~~~^~~~~~~~~~~~
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 |     for(int k=0;k<(1<<lg)&&(ait+k)<a.size();k++){
      |                            ~~~~~~~^~~~~~~~~
swap.cpp:33:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int k=0;k<(1<<lg)&&(bit+k)<b.size();k++){
      |                            ~~~~~~~^~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:129:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 | for(int i=0;i<seq.size();i++){
      |             ~^~~~~~~~~~~
swap.cpp:132:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 | for(int i=0;i<dp[1][ar[1]].size();i++){
      |             ~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 0 / 32