Submission #335060

#	Time	Username	Problem	Language	Result	Execution time	Memory
335060		limabeans	Swap (BOI16_swap)	C++17	100 / 100	289 ms	28652 KiB

swap

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


int n;
int p[maxn];

map<pair<int,int>,int> dp;

int test(int i, int carry) {
    pair<int,int> key={i,carry};
    if (dp.count(key)) return dp[key];
    
    if (2*i>n) {
	return dp[key]=i;
    }
    if (2*i+1>n) {
	if (carry<p[2*i]) {
	    return dp[key]=i;
	} else {
	    return dp[key]=2*i;
	}
    }

    if (carry<min(p[2*i],p[2*i+1])) {
	return dp[key]=i;
    }
    if (p[2*i]<min(carry,p[2*i+1])) {
	return dp[key]=test(2*i,carry);
    }

    assert(p[2*i+1]<min(carry,p[2*i]));
    //obviously swap in p[2*i+1] into p[i]
    //but it's unclear if before getting to 2*i+1 we want to swap 2*i with i as well.
    int lo = min(carry,p[2*i]);
    if (test(2*i,lo)<test(2*i+1,lo)) {
	if (lo==carry) {
	    return dp[key]=test(2*i,carry);
	} else {
	    return dp[key]=test(2*i+1,carry);
	}
    } else {
	if (lo==carry) {
	    return dp[key]=test(2*i+1,carry);
	} else {
	    return dp[key]=test(2*i,carry);
	}
    }
}



void solve(int i) {
    if (2*i>n) {
	return;
    }
    if (2*i+1>n) {
	if (p[i]>p[2*i]) {
	    swap(p[i],p[2*i]);
	}
	return;
    }
    if (p[i]<min(p[2*i],p[2*i+1])) {
	// do nothing
    } else if (p[2*i]<min(p[i],p[2*i+1])) {
	swap(p[i],p[2*i]);
    } else {
	assert(p[2*i+1]<min(p[i],p[2*i]));

	int lo = min(p[i],p[2*i]);
	int hi = max(p[i],p[2*i]);
	
	p[i]=p[2*i+1];
	
	if (test(2*i,lo)<test(2*i+1,lo)) {
	    p[2*i]=lo;
	    p[2*i+1]=hi;
	} else {
	    p[2*i]=hi;
	    p[2*i+1]=lo;
	}
	
	
    }
    solve(i+1);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    for (int i=1; i<=n; i++) {
	cin>>p[i];
    }


    solve(1);

    for (int i=1; i<=n; i++) {
	cout<<p[i]<<" ";
    }
    cout<<endl;    
    return 0;
}

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