Submission #60409

#	Time	Username	Problem	Language	Result	Execution time	Memory
60409		junodeveloper	medians (balkan11_medians)	C++17	10 / 100	94 ms	7928 KiB

medians

#include <bits/stdc++.h>
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(), (x).end()
using namespace std;
struct Z {
	int i,x,y;
};
int n, b[100010], a[200010], p[100010][2], sz[100010];
bool chk[200010];
vector<Z> V1,V2;
int main() {
	scanf("%d", &n);
	for(int i=1; i<=n; i++) {
		scanf("%d", b+i);
		if(i == 1) chk[b[i]] = 1;
		else {
			if(b[i] == b[i-1]) {
				V1.push_back({i,b[i-1],1});
				V2.push_back({i,b[i-1],1});
			}
			else if(b[i] > b[i-1]) V2.push_back({i,b[i-1],2});
			else V1.push_back({i,b[i-1],2});
		}
	}
	sort(ALL(V1), [&](const Z& a, const Z& b) {
		return a.x < b.x;
	});
	sort(ALL(V2), [&](const Z& a, const Z& b) {
		return a.x > b.x;
	});
	int c1 = 1, c2 = 2*n-1;
	for(auto& it : V1) {
		for(int j=0; j<it.y; j++) {
			while(chk[c1]) c1++;
			chk[c1] = 1, p[it.i][sz[it.i]++] = c1;
		}
	}
	for(auto& it : V2) {
		for(int j=0; j<it.y; j++) {
			while(chk[c2]) c2--;
			chk[c2] = 1, p[it.i][sz[it.i]++] = c2;
		}
	}
	a[1] = b[1];
	for(int i=2; i<=n; i++) {
		a[2*(i-1)] = p[i][0];
		a[2*(i-1)+1] = p[i][1];
	}
	for(int i=1; i<2*n; i++) printf("%d ", a[i]);
	return 0;
}

Compilation message (stderr)

medians.cpp: In function 'int main()':
medians.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
medians.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", b+i);
   ~~~~~^~~~~~~~~~~

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