Submission #94343

#	Time	Username	Problem	Language	Result	Execution time	Memory
94343		Noam527	medians (balkan11_medians)	C++17	100 / 100	34 ms	4404 KiB

medians

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
using namespace std;

void debug(string names) {
	cout << '\n';
}
template<typename A1, typename... A2>
void debug(string names, A1 par, A2... left) {
	int pos = 0;
	for (; pos < names.size() && names[pos] != ' ' && names[pos] != ','; pos++)
		cout << names[pos];
	cout << ": " << par << "  ";
	while (pos < names.size() && (names[pos] == ' ' || names[pos] == ',')) {
		pos++;
	}
	names.erase(names.begin(), names.begin() + pos);
	debug(names, left...);
}

struct fenwick {
	int n;
	vector<int> tree;
	fenwick() {}
	fenwick(int sz) {
		n = sz + 1;
		tree.resize(n, 0);
	}
	void upd(int pos) {
		for (pos++; pos <= n; pos += (pos & -pos)) tree[pos]++;
	}
	int query(int pos) {
		int rtn = 0;
		for (pos++; pos; pos -= (pos & -pos)) rtn += tree[pos];
		return rtn;
	}
	int query(int l, int r) {
		return query(r) - query(l - 1);
	}
};

int n, a[100005], used[200005] = {}, ans[200005];
int L, R;
fenwick F;

int nxtl() {
	while (used[L]) L++;
	return L;
}
int nxtr() {
	while (used[R]) R--;
	return R;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	F = fenwick(2 * n);
	for (int i = 0; i < n; i++) cin >> a[i], --a[i];
	L = 0, R = 2 * (n - 1);
	ans[0] = a[0];
	used[ans[0]] = 1;
	F.upd(ans[0]);
	for (int i = 1; i < n; i++) {
		int cur = F.query(a[i] - 1);
		if (!used[a[i]]) {
			ans[2 * i - 1] = a[i];
			used[ans[2 * i - 1]] = 1;
			F.upd(ans[2 * i - 1]);
			if (cur == i - 1) {
				ans[2 * i] = nxtl();
			}
			else {
				ans[2 * i] = nxtr();
			}
			used[ans[2 * i]] = 1;
			F.upd(ans[2 * i]);
		}
		else {
			if (cur == i - 2) {
				ans[2 * i - 1] = nxtl();
				used[ans[2 * i - 1]] = 1;
				F.upd(ans[2 * i - 1]);
				ans[2 * i] = nxtl();
				used[ans[2 * i]] = 1;
				F.upd(ans[2 * i]);
			}
			else if (cur == i) {
				ans[2 * i - 1] = nxtr();
				used[ans[2 * i - 1]] = 1;
				F.upd(ans[2 * i - 1]);
				ans[2 * i] = nxtr();
				used[ans[2 * i]] = 1;
				F.upd(ans[2 * i]);
			}
			else {
				ans[2 * i - 1] = nxtl();
				used[ans[2 * i - 1]] = 1;
				F.upd(ans[2 * i - 1]);
				ans[2 * i] = nxtr();
				used[ans[2 * i]] = 1;
				F.upd(ans[2 * i]);
			}
		}
	}
	for (int i = 0; i < 2 * n - 1; i++) cout << 1 + ans[i] << " "; cout << '\n';
}

Compilation message (stderr)

medians.cpp: In function 'int main()':
medians.cpp:110:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (int i = 0; i < 2 * n - 1; i++) cout << 1 + ans[i] << " "; cout << '\n';
  ^~~
medians.cpp:110:65: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (int i = 0; i < 2 * n - 1; i++) cout << 1 + ans[i] << " "; cout << '\n';
                                                                 ^~~~

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