QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#32617 | #866. Display of Springs | AutumnKite | TL | 0ms | 3536kb | C++17 | 1.9kb | 2022-05-22 13:24:45 | 2022-05-22 13:24:46 |
Judging History
answer
#include <bits/stdc++.h>
const int LIM = 6;
int compare(int i, int j, int x) {
std::cout << "? " << i << " " << j << " " << x << std::endl;
std::string tmp;
std::cin >> tmp;
if (tmp == "FIRST") {
return 1;
} else if (tmp == "SECOND") {
return -1;
} else {
return 0;
}
}
class lichao_tree {
struct node {
node *ls, *rs;
int id;
node(int t_id) : ls(), rs(), id(t_id) {}
};
node *rt;
void insert(node *&u, int l, int r, int id) {
if (u == nullptr) {
u = new node(id);
return;
}
if (l == r) {
if (compare(id, u->id, l) > 0) {
u->id = id;
return;
}
}
int mid = (l + r) >> 1;
if (compare(id, u->id, mid) > 0) {
std::swap(id, u->id);
}
if (compare(id, u->id, l) > 0) {
insert(u->ls, l, mid, id);
} else {
insert(u->rs, mid + 1, r, id);
}
}
int query(node *u, int l, int r, int x) {
if (u == nullptr) {
return -1;
}
if (l == r) {
return u->id;
}
int mid = (l + r) >> 1;
int res;
if (x <= mid) {
res = query(u->ls, l, mid, x);
} else {
res = query(u->rs, mid + 1, r, x);
}
if (res == -1 || compare(u->id, res, x) > 0) {
return u->id;
} else {
return res;
}
}
public:
lichao_tree(int n) : rt() {
for (int i = 0; i < n; ++i) {
insert(rt, 1, LIM, i);
}
std::cout << "!" << std::endl;
}
void query(int x) {
int res = query(rt, 1, LIM, x);
std::cout << "! " << res << std::endl;
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
lichao_tree T(n);
while (true) {
std::string tmp;
std::cin >> tmp;
if (tmp == "FINISH") {
return 0;
}
int x;
std::cin >> x;
T.query(x);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
input:
3 FIRST SECOND SECOND SECOND FIRST SECOND QUESTION 2 QUESTION 6 FIRST SECOND FINISH
output:
? 1 0 3 ? 0 1 1 ? 2 1 3 ? 2 1 1 ? 2 0 5 ? 0 2 4 ! ! 1 ? 2 0 6 ? 1 2 6 ! 2
result:
ok Correct answer
Test #2:
score: -100
Time Limit Exceeded
input:
6 FIRST EQUAL FIRST FIRST EQUAL SECOND FIRST SECOND SECOND SECOND FIRST EQUAL FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND QUESTION 1 SECOND QUESTION 2 EQUAL QUESTION 3 FIRST QUESTION 4 SECOND QUESTION 5 SECOND QUESTION 6 FIRST SECOND QUESTION 7 FIRST SECOND QUESTION 10 FIRST SECOND QUESTI...
output:
? 1 0 3 ? 0 1 1 ? 2 1 3 ? 1 2 1 ? 3 2 3 ? 3 2 1 ? 3 0 5 ? 0 3 4 ? 4 2 3 ? 4 2 1 ? 4 3 5 ? 3 4 4 ? 3 0 6 ? 5 2 3 ? 5 2 1 ? 5 4 5 ? 5 4 4 ? 5 3 6 ? 5 3 6 ? 5 3 6 ! ? 2 1 1 ! 1 ? 2 1 2 ! 1 ? 2 1 3 ! 2 ? 2 4 4 ! 4 ? 2 4 5 ! 4 ? 4 3 6 ? 2 4 6 ! 4 ? 4 3 7 ? 2 4 7 ! 4 ? 4 3 10 ? 2 4 10 ! 4 ? 4 3 1000 ? 2 4...