oj.uz

Submission #414086

# Submission time Handle Problem Language Result Execution time Memory
414086 2021-05-30T01:15:17 Z Blagojce Swap (BOI16_swap) C++11
0 / 100
 34 ms 44920 KB 
#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 = 400000;
 
int n;
int a[mxn];
 
 
unordered_map<int, vector<int> > f[mxn];
//vector<int> f[mxn][mxn];
 
vector<int> combine(int a, int x, int b, int y){
	int p = 0;
	int l = 1;
	
	vector<int> ret;
	while(p < (int)f[a][x].size()){
		fr(k, 0, l){
			ret.pb(f[a][x][p+k]);
		}
		fr(k, 0, l){
			ret.pb(f[b][y][p+k]);
		}
		p += l;
		l *= 2;
	}
	
	return ret;
}
vector<int> lex(vector<int> v1, vector<int> v2){
	fr(i, 0, (int)v1.size()){
		if(v1[i] < v2[i]) return v1;
		else if(v1[i] > v2[i]) return v2;
	}
	return v1;
}
 
void solve(){
	cin >> n;
	fr(i, 1, n+1){
		cin >> a[i];
	}
	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;
	
	for(int i = n; i >= 1; i --){
		vector<int> cand;
		int mx = 0;
		for(int j = i; j >= 1; j /= 2){
			mx = max(mx, a[j]);
			//cand.pb(a[j]);
			if(j != 1){
				if(j % 2){
					mx = max(mx, a[j-1]);
					//cand.pb(a[j-1]);
				}
				else{
					mx = max(mx, a[j+1]);
					//cand.pb(a[j+1]);
				}
			}
		}
		cand.pb(mx);
		if(i != 1){
			if(i%2) cand.pb(a[i-1]);
			else cand.pb(a[i+1]);
		}
		
		for(auto j : cand){
			if(i*2 > n){
				f[i][j] = {j};
			}
			else{
				int mi = min(j, min(a[i*2], a[i*2+1]));
				if(j == mi){
					f[i][j] = combine(i*2, a[i*2], i*2+1, a[i*2+1]);
				}
				else if(a[i*2] == mi){
					f[i][j] = combine(i*2, j, i*2+1, a[i*2+1]);
				}
				else{
					vector<int> g1 = combine(i*2, a[i*2], i*2+1, j);
					vector<int> g2 = combine(i*2, j, i*2+1, a[i*2]);
					f[i][j] = min(g1, g2);
				}
				f[i][j].insert(f[i][j].begin(), mi);	
			}
		}
	}
	fr(i, 0, orgn){
		cout<<f[1][a[1]][i]<<' ';
	}	
}
 
int main(){
	//freopen("t.in.25", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}
//

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 44920 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 44920 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 44920 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 44920 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 44920 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -