Submission #414349

#	Time	Username	Problem	Language	Result	Execution time	Memory
414349		Blagojce	Swap (BOI16_swap)	C++11	0 / 100	9 ms	12624 KiB

swap

#include <bits/stdc++.h>
#include <cstdio>
#pragma GCC optimize("O3")
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 262144 + 10;
 
inline int readint(){
	int ret=0;
	for(char c;;){
		c=getchar();
		if('0'<=c and c<='9')
			ret=ret*10+(c&15);
		else
			return ret;
	}
}
vector<char> digits;
inline void printint(int x){
	do{
		digits.push_back(x%10|48);
		x/=10;
	}while(x);
	while(not digits.empty())
		putchar(digits.back()), digits.pop_back();
}
 
 
int n;
int a[mxn];
 
 
map<int, vector<int> > f[mxn];
int p, l;
int p2;

int mi;

void combine(vector<int> &v1, vector<int> &v2, vector<int> &r){
	r.reserve(2*(int)v1.size());
	p = 0;
	p2 = 0;
	l = 1;
	
	while(p < (int)v1.size()){
		fr(k, 0, l){
			r[p2++] = v1[p+k];
		}
		fr(k, 0, l){
			r[p2++] = v2[p+k];
		}
		p += l;
		l *= 2;
	}
}
 

 
vector<int> g1;
vector<int> g2;
vector<int> cand;

void rec(int k){
	
	cand.pb(a[k]);
	if(k != 1){
		if(k%2) cand.pb(a[k-1]);
		else cand.pb(a[k+1]);
	}
	
	
	if(k*2 > n){
		for(auto u : cand){
			f[k][u] = {u};
		}
		cand.pop_back();
		if(k != 1){
			cand.pop_back();
		}
		return;
	}
	
	rec(k*2);
	rec(k*2+1);
	
	
	for(auto j : cand){
		
		mi = min(j, min(a[k*2], a[k*2+1]));
		
		if(j == mi){
			f[k][j] = {mi};
			combine(f[k*2][a[k*2]], f[k*2+1][a[k*2+1]], f[k][j]);
		}
		else if(a[k*2] == mi){
			f[k][j] = {mi};
			combine(f[k*2][j], f[k*2+1][a[k*2+1]], f[k][j]);
		}
		else{
			g1.clear();
			g1.pb(mi);
			combine(f[k*2][a[k*2]], f[k*2+1][j], g1);
			g2.clear();
			g2.pb(mi);
			combine(f[k*2][j], f[k*2+1][a[k*2]], g2);
			f[k][j] = min(g1, g2);
		}
	}
	cand.pop_back();
	if(k != 1){
		cand.pop_back();
	}
	f[2*k].clear();
	f[2*k+1].clear();
}

 
void solve(){
	n = readint();
	fr(i, 1, n+1){
		a[i] = readint();
	}
	int orgn = n;
	int m = n;
	while(m+1 - ((m+1)&-(m+1)) != 0){	
		++m;
	}
	
	fr(i, n+1, m+1){
		a[i] = i;
	}
	n = m;
	rec(1);
	
	vector<int> ans = f[1][a[1]];
	fr(i, 0, orgn){
		printint(ans[i]);
		putchar(' ');
	}	
}
 
int main(){
	digits.reserve(10);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

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