This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 int 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 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(ll i=0;i<need[a].size();i++){
| ~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |