Submission #94343

# Submission time Handle Problem Language Result Execution time Memory
94343 2019-01-17T20:01:44 Z Noam527 medians (balkan11_medians) C++17
100 / 100
34 ms 4404 KB
#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

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';
                                                                 ^~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 6 ms 888 KB Output is correct
5 Correct 12 ms 1784 KB Output is correct
6 Correct 21 ms 2936 KB Output is correct
7 Correct 34 ms 4404 KB Output is correct