| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 779099 |
2023-07-11T07:50:26 Z |
박영우(#10003) |
Tram (CEOI13_tram) |
C++17 |
|
54 ms |
11584 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;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
8120 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
8100 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
2328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
11584 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
864 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
