Submission #1248000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248000		kaiboy	Tram (CEOI13_tram)	C++20	0 / 100	15 ms	4168 KiB

tram

#include <algorithm>
#include <iostream>
#include <set>

using namespace std;

const int N = 150000;
const int M = 30000;
const int INF = 0x3f3f3f3f;

bool used[N << 1];
int ii_[M], n;
set<int> ii;
set<pair<int, pair<int, int>>> pp;

int dist(int i, int j) {
	return i == -2 || j == -2 ? -1 : i == -1 || j == n << 1 ? INF : i >> 1 == j >> 1 ? 2 : (j >> 1) - (i >> 1) << 1 ^ (i & 1) != (j & 1);
}

int dist_(int i, int l, int r) {
	if (i == -2)
		return -1;
	int ans = min(dist(l, i), dist(i, r));
	if (l >= 0 && used[l ^ 1])
		ans = min(ans, dist(l ^ 1, i));
	if (r < n << 1 && used[r ^ 1])
		ans = min(ans, dist(i, r ^ 1));
	return ans;
}

int calc(int i, int j) {
	if (j - i == 1)
		return -2;
	if (i == -1 && j == n << 1)
		return 0;
	if (i == -1)
		return used[j ^ 1] ? 0 : j & 1 ^ 1;
	if (j == n << 1)
		return used[i ^ 1] ? n - 1 << 1 : n - 1 << 1 ^ i & 1 ^ 1;
	i >>= 1, j >>= 1;
	bool a = used[i << 1 ^ 0], b = used[i << 1 ^ 1];
	bool c = used[j << 1 ^ 0], d = used[j << 1 ^ 1];
	if (j - i & 1) {
		if (j - i == 1)
			return !b ? i << 1 ^ 1 : j << 1 ^ 0;
		return i + j >> 1 << 1 ^ (a && !b);
	}
	if (a && !b && c && !d)
		return i + j ^ 1;
	if (j - i == 2 && !b)
		return i << 1 ^ 1;
	return i + j;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int q; cin >> n >> q;
	ii.insert(-1), ii.insert(n << 1);
	pp.insert({ dist_(calc(-1, n << 1), -1, n << 1), { -1, n << 1 } });
	for (int h = 0; h < q; h++) {
		char c; cin >> c;
		if (c == 'E') {
			auto dlr = *pp.begin(); pp.erase(dlr);
			int l = dlr.second.first, r = dlr.second.second;
			int i = calc(l, r);
			used[ii_[h] = i] = true, ii.insert(i);
			pp.insert({ -dist_(calc(l, i), l, i), { l, i } });
			pp.insert({ -dist_(calc(i, r), i, r), { i, r } });
			cout << (i >> 1) + 1 << ' ' << (i & 1) + 1 << '\n';
		} else {
			int g; cin >> g, g--;
			int i = ii_[g];
			auto it = ii.lower_bound(i);
			int l = *prev(it), r = *next(it);
			pp.erase({ -dist_(calc(l, i), l, i), { l, i } });
			pp.erase({ -dist_(calc(i, r), i, r), { i, r } });
			used[i] = false, ii.erase(i);
			pp.insert({ -dist_(calc(l, r), l, r), { l, r } });
		}
	}
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 20