Submission #1012466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012466		hengliao	Swap (BOI16_swap)	C++17	100 / 100	924 ms	260276 KiB

swap

#include<bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;

const ll mxN=2e5+5;
const ll LOG=20;

struct node{
    node *lef, *rig;
    ll val;

    node(node *lf, node *rg, ll vl){
        lef=lf;
        rig=rg;
        val=vl;
    }

    bool compare(const node *tar){
        vll v1, v2;
        queue<const node*> q;
        q.push(this); 
        while(!q.empty()){
            const node *cur=q.front(); q.pop();
            v1.pb(cur->val);
            if(cur->lef!=nullptr){
                q.push(cur->lef);
            }
            if(cur->rig!=nullptr){
                q.push(cur->rig);
            }
        }
        q.push(tar);
        while(!q.empty()){
            const node *cur=q.front(); q.pop();
            v2.pb(cur->val);
            if(cur->lef!=nullptr){
                q.push(cur->lef);
            }
            if(cur->rig!=nullptr){
                q.push(cur->rig);
            }
        }
        /*cout<<"comparing\n";
        for(auto &it:v1){
            cout<<it<<' ';
        }
        cout<<'\n';
        for(auto &it:v2){
            cout<<it<<' ';
        }
        cout<<'\n';
        cout<<(v1<v2);
        cout<<"done\n";*/
        return v1<v2;
    }

    void prt(){
        vll v1;
        queue<const node*> q;
        q.push(this); 
        while(!q.empty()){
            const node *cur=q.front(); q.pop();
            v1.pb(cur->val);
            if(cur->lef!=nullptr){
                q.push(cur->lef);
            }
            if(cur->rig!=nullptr){
                q.push(cur->rig);
            }
        }
        for(auto &it:v1){
            cout<<it<<' ';
        }
        cout<<'\n';
    }
};

vector<node*> dp[mxN];
vll need[mxN];
ll n;
ll arr[mxN];

ll getidx(ll a, ll b){
    for(ll i=0;i<need[a].size();i++){
        if(need[a][i]==b){
            return i;
        }
    }
    return -1;
}

node* f(ll a, ll b){
    ll idx=getidx(a, b);
    if(idx!=-1){
        return dp[a][idx];
    }
    if(2*a>n){
        need[a].pb(b);
        node *tep=new node(nullptr, nullptr, b);
        dp[a].pb(tep);
        return tep;
    }
    if(2*a+1>n){
        if(b<arr[2*a]){
            need[a].pb(b);
            node *tep=new node(f(2*a, arr[2*a]), nullptr, b);
            dp[a].pb(tep);
            return tep;
        }
        else{
            need[a].pb(b);
            node *tep=new node(f(2*a, b), nullptr, arr[2*a]);
            dp[a].pb(tep);
            return tep;
        }
    }
    if(b<arr[2*a] && b<arr[2*a+1]){
        need[a].pb(b);
        node *tep=new node(f(2*a, arr[2*a]), f(2*a+1, arr[2*a+1]), b);
        dp[a].pb(tep);
        return tep;
    }
    if(arr[2*a]<b && arr[2*a]<arr[2*a+1]){
        need[a].pb(b);
        node *tep=new node(f(2*a, b), f(2*a+1, arr[2*a+1]), arr[2*a]);
        dp[a].pb(tep);
        return tep;
    }
    need[a].pb(b);
    node *tep1=new node(f(2*a, b), f(2*a+1, arr[2*a]), arr[2*a+1]);
    node *tep2=new node(f(2*a, arr[2*a]), f(2*a+1, b), arr[2*a+1]);
    //tep1->prt();
    //tep2->prt();
    if(tep1->compare(tep2)){
        dp[a].pb(tep1);
        
    }
    else{
        dp[a].pb(tep2);
        //cout<<"h1\n";
    }
    //dp[a].pb(min(tep1, tep2));
    return dp[a].back();
}

void solve(){
	cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>arr[i];
    }
    node *re=f(1, arr[1]);
    /*for(ll i=1;i<=n;i++){
        for(ll j=0;j<need[i].size();j++){
            cout<<"dp "<<i<<' '<<need[i][j]<<'\n';
            dp[i][j]->prt();
        }
    }
    cout<<"_________\n";*/
    re->prt();
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	solve();
	return 0;
}

Compilation message (stderr)

swap.cpp: In function 'll getidx(ll, ll)':
swap.cpp:92:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(ll i=0;i<need[a].size();i++){
      |                ~^~~~~~~~~~~~~~~

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