Submission #1047831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047831		vjudge1	medians (balkan11_medians)	C++17	100 / 100	25 ms	4444 KiB

medians

// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)3e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;

int n;
int a[MAX],b[MAX];
bool vis[MAX];

// - Lower[i] = i - 1;
// - Upper[i] = 2 * n + 1 - i
// 
// // tuc la lower + upper co (2 * i - 2) phan tu.
// (low[i] < bi < upper)
// 
// - thg thu i co 2*i - 1 phan tu nen median thu i kh the be hon i - 1 hoac lon hon 2 * n - i + 1
// 
// vminx = 1,vmax = 2 * n - 1.
// adding vminx when vminx <= low(i) or vmax when vmax >= upper(i) wont interfere the value of medians after index i 

signed main(){
	
	int n;
	cin >> n;
	int vmin = 1;
	int vmax = 2 * n - 1;
	
	for(int i = 1;i <= n;i++){
		cin >> b[i];
		
		if(i == 1){
			a[i] = b[i];
			vis[a[i]] = 1;
			continue;
		}	
		
		if(b[i - 1] == b[i]){
			// bi = bi - 1 : 
			// - gia su (1 -> lower(i)) o trong tap (vmin > lower) -> median b(i - 1) must be (i - 1) ? prove that ?? ( boi vi i - 2 phan tu o trong tap nen phan tu thu i - 1 la i - 1) luon. 
			// - Nhung bi kh the la i - 1 boi bi i - 1 = lower(i).
			// --> cta kh the co bi = b(i -1). 
			// Vi vay nen cac so tu (1 -> lower(i)) se chua duoc dung trong (2 * (i - 1) - 1) phan tu dau. -> vmin <= lower(i) 
		
			while(vis[vmin])++vmin;
			a[i * 2 - 2] = vmin;
			vis[vmin] = 1;
			while(vis[vmax])vmax--;
			a[i * 2 - 1] = vmax;
			vis[vmax] = 1;
		}else if(b[i - 1] > b[i]){
			if(!vis[b[i]]){
				
				// 2.1 : bi doesn't appear as median before the index i 
				// - gia su gia thiet la dung voi i - 1 medians va hi vong no dung voi i medians. -> vmin va vmax != bi. 
				// thus b(i) kh xuat hien trong (1 -> 2 * (i - 1) - 1) , add vao. 

				a[i * 2 - 2] = b[i];
				vis[b[i]] = 1;
				while(vis[vmin])vmin++;
				a[i * 2 - 1] = vmin;
				vis[vmin] = 1;
				
			}else{
				// 2.2 : bi appeared as a median in previous .. 
				// - luc nay thi tu 1 -> i - 1 chac chan con thieu it nhat la 2 vi tri ?? prove ? neu 1 -> i - 1 deu xuat hien trong premutation thi ? bi > bi + .
				// -> add 2 lan vmin 

				while(vis[vmin])vmin++;
				a[i * 2 - 2] = vmin;
				vis[vmin] = 1;
				while(vis[vmin])vmin++;
				a[i * 2 - 1] = vmin;
				vis[vmin] = 1;
			}
		}else{
			if(!vis[b[i]]){
				a[i * 2 - 2] = b[i];
				vis[b[i]] = 1;
				while(vis[vmax])vmax--;
				a[i * 2 - 1] = vmax;
				vis[vmax] = 1;
			}else{
				while(vis[vmax])vmax--;
				a[i * 2 - 1] = vmax;
				vis[vmax] = 1;
				while(vis[vmax])vmax--;
				a[i * 2 - 2] = vmax;
				vis[vmax] = 1;
			}
		}
	}	
	
	for(int i = 1;i <= 2 * n - 1;i++)cout << a[i] << " \n"[i == 2 * n - 1];
}

• Subtask 1: 65 / 65
• Subtask 2: 35 / 35