oj.uz

답안 #779100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
779100 2023-07-11T07:51:47 Z 박영우(#10003) 전차 (CEOI13_tram) C++17
100 / 100
 58 ms 11636 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010101
#define MAXS 22
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif
int chk[MAX];
pii ind[MAX];
set<pair<int, pii>> st;
set<int> all;
int N, M;
int dis(pii p1, pii p2) {
	int d = abs(p2.first - p1.first);
	return d * 2 + p1.second ^ p2.second;
}
int getd(int l, int r) {
	if (!chk[l] && !chk[r]) return 1e9;
	if (!chk[l]) { //0
		if (chk[r] == 3) return 2 * (r - 1);
		else return 2 * (r - 1) + 1;
	}
	if (!chk[r]) {
		if (chk[l] == 3) return 2 * (N - l);
		else return 2 * (N - l) + 1;
	}
	int len = r - l;
	if (len & 1) {
		len >>= 1;
		if (chk[l] == 3 && chk[r] == 3) return len * 2;
		else return len * 2 + 1;
	}
	else {
		len >>= 1;
		if (chk[l] == 3 || chk[r] == 3) return len * 2;
		else if (chk[l] != chk[r]) return len * 2;
		return len * 2 + 1;
	}
}
pii get(int l, int r) {
	if (!chk[l] && !chk[r]) return pii(1, 0);
	if (!chk[l]) { //0
		if (chk[r] == 1) return pii(1, 1);
		else return pii(1, 0);
	}
	if (!chk[r]) {
		if (chk[l] == 1) return pii(N, 1);
		else return pii(N, 0);
	}
	int len = r - l;
	int m = l + r >> 1;
	if (len & 1) {
		if (chk[l] == 3 && chk[r] == 3) return pii(m, 0);
		else if (chk[l] == 3) {
			if (chk[r] == 1) return pii(m + 1, 1);
			else return pii(m + 1, 0);
		}
		else {
			if (chk[l] == 1) return pii(m, 1);
			else return pii(m, 0);
		}
	}
	else {
		if (chk[l] == 1 && chk[r] == 1) return pii(m, 1);
		else return pii(m, 0);
	}
}
pii operator-(pii p) { return pii(-p.first, -p.second); }
pair<int, pii> get(int x) {
	int pv, ne;
	auto it = all.lower_bound(x);
	if (*it == x) return { -1, {-1, -1} };
	ne = *it;
	pv = *--it;
	return make_pair(getd(pv, ne), -pii(pv, ne));
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> N >> M;
	int i;
	all.insert(0);
	all.insert(N + 1);
	st.emplace((N + 1) * 2, pii(0, N + 1));
	set<int> zst, ost, tst;
	for (i = 1; i <= N; i++) zst.insert(i);
	for (i = 1; i <= M; i++) {
		char c;
		cin >> c;
		if (c == 'L') {
			int x;
			cin >> x;
			st.erase(get(ind[x].first - 1));
			st.erase(get(ind[x].first + 1));
			chk[ind[x].first] ^= (1 << ind[x].second);
			if (!chk[ind[x].first]) ost.erase(ind[x].first), zst.insert(ind[x].first);
			else tst.erase(ind[x].first), ost.insert(ind[x].first);
			if (!chk[ind[x].first]) {
				all.erase(ind[x].first);
				auto r = get(ind[x].first);
				if (~r.first) st.insert(r);
			}
			else {
				auto r1 = get(ind[x].first - 1);
				auto r2 = get(ind[x].first + 1);
				if (~r1.first) st.insert(r1);
				if (~r2.first) st.insert(r2);
			}
		}
		else {
			int addx;
			int c = 1;
			if (zst.size()) {
				auto x = *st.rbegin();
				if (x.first == 2) {
					auto res = get(-x.second.first, -x.second.second);
					if (ost.size() && *ost.begin() < res.first) c = 0;
				}
			}
			else c = 0;
			if (c) {
				auto x = *st.rbegin();
				st.erase(x);
				int l, r;
				l = -x.second.first;
				r = -x.second.second;
				ind[i] = get(l, r);
				chk[ind[i].first] ^= (1 << ind[i].second);
				if (chk[ind[i].first] != 3) all.insert(ind[i].first);
				auto r1 = get(ind[i].first - 1);
				auto r2 = get(ind[i].first + 1);
				if (~r1.first) st.insert(r1);
				if (~r2.first) st.insert(r2);
				addx = ind[i].first;
			}
			else {
				addx = *ost.begin();
				if (chk[addx] == 1) ind[i] = pii(addx, 1);
				else ind[i] = pii(addx, 0);
				chk[addx] = 3;
			}
			if (chk[addx] == 3) ost.erase(addx), tst.insert(addx);
			else zst.erase(addx), ost.insert(addx);
			cout << ind[i].first << bb << ind[i].second + 1 << ln;
		}
	}
}

Compilation message

tram.cpp: In function 'int dis(pii, pii)':
tram.cpp:27:15: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   27 |  return d * 2 + p1.second ^ p2.second;
      |         ~~~~~~^~~~~~~~~~~
tram.cpp: In function 'pii get(int, int)':
tram.cpp:63:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |  int m = l + r >> 1;
      |          ~~^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 8140 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 25 ms 7940 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 8040 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 25 ms 8008 KB Output is correct

Subtask #7
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 2388 KB Output is correct
2 Correct 17 ms 904 KB Output is correct
3 Correct 24 ms 2348 KB Output is correct

Subtask #8
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 11636 KB Output is correct
2 Correct 16 ms 776 KB Output is correct
3 Correct 51 ms 9292 KB Output is correct