CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)
CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)
제대로(?) 처음 참가해본 엣코더
600점 겟
빨리 풀고 $G$는 그냥 던지고 갔지만 1900점대 퍼포가 나왔다. 코포로 치면 오렌지퍼포인것같다.
업솔빙은 $G$만 의미있을것같다.
A. New Scheme (-881)
그냥 해주면 된다.
B. Default Price (-417)
딕셔너리를 이용해서 잘 구현해주면 된다.
C. Standings (605)
그냥 정렬해주는 문제
D. Snuke Maze (619)
BFS 기본 문제
E. MEX (1042)
DP로 뒤에서부터 X인데 0,1,2 인 것의 개수와 E인데 총 $8$가지 어떤 수들이 나왔었는지 여부를 검사해주면 M이 나왔을 때 E의 개수에 따라 MEX를 구해서 정답에 더해주면 된다.
F. Vouchers (1284)
가장 $D_i$가 큰 쿠폰들부터 보면서 현재 아이템들 중 $L_i$ 이상인 가장 작은것부터 사용해주면 된다.
G. Minimum Xor Pair Query (2008)
$x<y<z$ 일 때, $\text{Min}(x \oplus y, y \oplus z) < x \oplus z$ 라고 주장한다.
$x,z$의 이진수 표현에서 큰 비트부터 같다가 처음으로 달라지는 비트를 $k$ 라고할 때, $x$는 거기가 $0$이고 $z$는 $1$이다.
그곳의 비트를 $2^k$ 라고 하자.
$y$도 $k+1$ 이상의 비트는 $x,z$와 같을 것이고 거기가 $0$이라면 $x \oplus y < 2^k$ 이다. 거기가 $1$이라면 $y \oplus z < 2^k$ 이다.
$x \oplus z \ge 2^k$ 이므로 증명된다.
따라서 set 같은것에 오름차순대로 수를 관리하며 인접한 것들의 $xor$ 값만 관리해주면 된다.
void solve() {
int q;
cin >> q;
int mn = INT_MAX;
pi mx_pair;
multiset<int> val, val_xor;
while (q--) {
int cmd, x;
cin >> cmd;
if (cmd == 1) {
cin >> x;
auto it = val.insert(x);
int prev = -1, nxt = -1;
auto it_nxt = it;
it_nxt++;
if (it_nxt != val.end()) nxt = *it_nxt;
if (it != val.begin()) {
--it;
prev = *it;
}
if (nxt != -1 && prev != -1) val_xor.erase(val_xor.find(prev ^ nxt));
if (nxt != -1) val_xor.insert(x ^ nxt);
if (prev != -1) val_xor.insert(x ^ prev);
} else if (cmd == 2) {
cin >> x;
auto it = val.erase(val.find(x));
int nxt = -1, prev = -1;
if (it != val.end()) nxt = *it;
if (it != val.begin()) {
--it;
prev = *it;
}
if (nxt != -1) val_xor.erase(val_xor.find(nxt ^ x));
if (prev != -1) val_xor.erase(val_xor.find(prev ^ x));
if (prev != -1 && nxt != -1)
val_xor.insert(prev ^ nxt);
} else {
cout << *val_xor.begin() << endl;
}
}
}
Comments