QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#32619 | #866. Display of Springs | AutumnKite | AC ✓ | 143ms | 3696kb | C++17 | 1.9kb | 2022-05-22 13:38:27 | 2022-05-22 13:38:28 |
Judging History
answer
#include <bits/stdc++.h>
const int LIM = 100000;
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: 4ms
memory: 3596kb
input:
3 FIRST SECOND FIRST FIRST QUESTION 2 SECOND QUESTION 6 FIRST FINISH
output:
? 1 0 50000 ? 0 1 1 ? 2 1 50000 ? 1 2 1 ! ? 2 1 2 ! 1 ? 2 1 6 ! 2
result:
ok Correct answer
Test #2:
score: 0
Accepted
time: 9ms
memory: 3544kb
input:
6 FIRST EQUAL FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST QUESTION 1 SECOND SECOND SECOND SECOND QUESTION 2 EQUAL SECOND SECOND SECOND QUESTION 3 FIRST EQUAL SECOND SECOND QUESTION 4 FIRST FIRST EQUAL SECOND QUESTION 5 FIRST...
output:
? 1 0 50000 ? 0 1 1 ? 2 1 50000 ? 1 2 1 ? 3 2 50000 ? 2 3 1 ? 2 1 25000 ? 1 2 1 ? 4 3 50000 ? 3 4 1 ? 3 2 25000 ? 2 3 1 ? 2 1 12500 ? 1 2 1 ? 5 4 50000 ? 4 5 1 ? 4 3 25000 ? 3 4 1 ? 3 2 12500 ? 2 3 1 ? 2 1 6250 ? 1 2 1 ! ? 2 1 1 ? 3 1 1 ? 4 1 1 ? 5 1 1 ! 1 ? 2 1 2 ? 3 1 2 ? 4 1 2 ? 5 1 2 ! 1 ? 2 1 3...
result:
ok Correct answer
Test #3:
score: 0
Accepted
time: 79ms
memory: 3528kb
input:
326 SECOND SECOND SECOND FIRST FIRST FIRST FIRST FIRST SECOND FIRST SECOND FIRST FIRST SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND FIRST SECOND SECOND SECOND SECOND FIRST SECOND FIRST SECOND FIRST SECOND SECOND SECOND SECOND SECOND FIRST SECOND FIRST SECOND SECOND SECOND FIR...
output:
? 1 0 50000 ? 1 0 1 ? 2 0 50000 ? 2 0 1 ? 3 0 50000 ? 0 3 1 ? 0 2 25000 ? 2 0 1 ? 4 3 50000 ? 4 3 1 ? 4 0 25000 ? 4 0 1 ? 4 2 12500 ? 2 4 1 ? 5 3 50000 ? 5 3 1 ? 5 1 75000 ? 5 1 50001 ? 6 3 50000 ? 6 3 1 ? 6 0 25000 ? 6 0 1 ? 7 3 50000 ? 7 3 1 ? 7 0 25000 ? 7 0 1 ? 7 6 37500 ? 7 6 25001 ? 8 3 50000 ...
result:
ok Correct answer
Test #4:
score: 0
Accepted
time: 14ms
memory: 3588kb
input:
19 FIRST SECOND SECOND SECOND FIRST SECOND SECOND SECOND FIRST SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND FIRST SECOND FIRST FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECON...
output:
? 1 0 50000 ? 0 1 1 ? 2 1 50000 ? 2 1 1 ? 2 0 75000 ? 0 2 50001 ? 3 1 50000 ? 3 1 1 ? 3 2 75000 ? 2 3 50001 ? 2 0 87500 ? 0 2 75001 ? 4 1 50000 ? 4 1 1 ? 4 3 75000 ? 4 3 50001 ? 4 2 87500 ? 4 2 75001 ? 4 0 93750 ? 4 0 87501 ? 5 1 50000 ? 5 1 1 ? 5 3 75000 ? 5 3 50001 ? 5 2 87500 ? 5 2 75001 ? 5 0 93...
result:
ok Correct answer
Test #5:
score: 0
Accepted
time: 105ms
memory: 3532kb
input:
500 FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND F...
output:
? 1 0 50000 ? 0 1 1 ? 2 1 50000 ? 1 2 1 ? 1 0 75000 ? 0 1 50001 ? 3 2 50000 ? 2 3 1 ? 2 1 75000 ? 1 2 50001 ? 1 0 87500 ? 0 1 75001 ? 4 3 50000 ? 4 3 1 ? 4 2 75000 ? 4 2 50001 ? 4 1 87500 ? 4 1 75001 ? 4 0 93750 ? 0 4 87501 ? 5 3 50000 ? 5 3 1 ? 5 2 75000 ? 5 2 50001 ? 5 1 87500 ? 5 1 75001 ? 5 4 93...
result:
ok Correct answer
Test #6:
score: 0
Accepted
time: 141ms
memory: 3696kb
input:
500 EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQUAL EQ...
output:
? 1 0 50000 ? 1 0 1 ? 2 0 50000 ? 2 0 1 ? 2 1 75000 ? 2 1 50001 ? 3 0 50000 ? 3 0 1 ? 3 1 75000 ? 3 1 50001 ? 3 2 87500 ? 3 2 75001 ? 4 0 50000 ? 4 0 1 ? 4 1 75000 ? 4 1 50001 ? 4 2 87500 ? 4 2 75001 ? 4 3 93750 ? 4 3 87501 ? 5 0 50000 ? 5 0 1 ? 5 1 75000 ? 5 1 50001 ? 5 2 87500 ? 5 2 75001 ? 5 3 93...
result:
ok Correct answer
Test #7:
score: 0
Accepted
time: 113ms
memory: 3696kb
input:
500 FIRST SECOND SECOND SECOND SECOND SECOND FIRST SECOND FIRST SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND FIRST SECOND FIRST SECOND SECOND SECON...
output:
? 1 0 50000 ? 0 1 1 ? 2 1 50000 ? 2 1 1 ? 2 0 75000 ? 2 0 50001 ? 3 1 50000 ? 1 3 1 ? 1 0 75000 ? 0 1 50001 ? 0 2 87500 ? 2 0 75001 ? 4 3 50000 ? 4 3 1 ? 4 1 75000 ? 4 1 50001 ? 4 0 87500 ? 4 0 75001 ? 4 2 93750 ? 2 4 87501 ? 5 3 50000 ? 5 3 1 ? 5 1 75000 ? 5 1 50001 ? 5 0 87500 ? 5 0 75001 ? 5 4 93...
result:
ok Correct answer
Test #8:
score: 0
Accepted
time: 143ms
memory: 3528kb
input:
500 SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND FIRST SECOND SECOND SECOND SECOND SECOND SECOND SECOND FIRST SECOND FIRST SECOND FIRST SECOND SECOND SEC...
output:
? 1 0 50000 ? 1 0 1 ? 2 0 50000 ? 2 0 1 ? 2 1 75000 ? 1 2 50001 ? 3 0 50000 ? 3 0 1 ? 3 2 75000 ? 3 2 50001 ? 3 1 87500 ? 1 3 75001 ? 4 0 50000 ? 4 0 1 ? 4 2 75000 ? 4 2 50001 ? 4 3 87500 ? 4 3 75001 ? 4 1 93750 ? 1 4 87501 ? 5 0 50000 ? 5 0 1 ? 5 2 75000 ? 5 2 50001 ? 5 3 87500 ? 5 3 75001 ? 5 4 93...
result:
ok Correct answer
Test #9:
score: 0
Accepted
time: 16ms
memory: 3548kb
input:
2 FIRST FIRST QUESTION 64500 QUESTION 22602 FIRST QUESTION 37446 FIRST QUESTION 97972 QUESTION 78630 QUESTION 75591 QUESTION 63328 QUESTION 64746 QUESTION 94532 QUESTION 51275 QUESTION 12189 FIRST QUESTION 64341 QUESTION 85825 QUESTION 63713 QUESTION 36778 FIRST QUESTION 27116 FIRST QUESTION 18630 F...
output:
? 1 0 50000 ? 0 1 1 ! ! 1 ? 1 0 22602 ! 1 ? 1 0 37446 ! 1 ! 1 ! 1 ! 1 ! 1 ! 1 ! 1 ! 1 ? 1 0 12189 ! 1 ! 1 ! 1 ! 1 ? 1 0 36778 ! 1 ? 1 0 27116 ! 1 ? 1 0 18630 ! 1 ! 1 ? 1 0 28074 ! 1 ! 1 ! 1 ? 1 0 39195 ! 1 ! 1 ? 1 0 1182 ! 1 ! 1 ! 1 ! 1 ? 1 0 7017 ! 1 ? 1 0 13589 ! 1 ! 1 ! 1 ? 1 0 48324 ! 1 ! 1 ! 1 ...
result:
ok Correct answer
Test #10:
score: 0
Accepted
time: 23ms
memory: 3580kb
input:
2 FIRST FIRST QUESTION 54311 QUESTION 8466 SECOND QUESTION 82055 QUESTION 65419 QUESTION 5271 SECOND QUESTION 4799 SECOND QUESTION 21521 FIRST QUESTION 66767 QUESTION 24897 FIRST QUESTION 69127 QUESTION 84527 QUESTION 23303 FIRST QUESTION 88924 QUESTION 56421 QUESTION 88108 QUESTION 74033 QUESTION 2...
output:
? 1 0 50000 ? 0 1 1 ! ! 1 ? 1 0 8466 ! 0 ! 1 ! 1 ? 1 0 5271 ! 0 ? 1 0 4799 ! 0 ? 1 0 21521 ! 1 ! 1 ? 1 0 24897 ! 1 ! 1 ! 1 ? 1 0 23303 ! 1 ! 1 ! 1 ! 1 ! 1 ? 1 0 25348 ! 1 ? 1 0 10105 ! 0 ! 1 ? 1 0 33359 ! 1 ? 1 0 49782 ! 1 ? 1 0 20392 ! 1 ! 1 ! 1 ? 1 0 4246 ! 0 ! 1 ? 1 0 8620 ! 0 ? 1 0 30435 ! 1 ? 1...
result:
ok Correct answer
Test #11:
score: 0
Accepted
time: 122ms
memory: 3620kb
input:
500 SECOND FIRST FIRST FIRST FIRST FIRST SECOND FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST SECOND FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST FIRST FIRST SECOND FIRST FIRST FIRST FIRST FIRST...
output:
? 1 0 50000 ? 1 0 1 ? 2 0 50000 ? 0 2 1 ? 0 1 25000 ? 1 0 1 ? 3 2 50000 ? 3 2 1 ? 3 0 25000 ? 0 3 1 ? 0 1 12500 ? 1 0 1 ? 4 2 50000 ? 2 4 1 ? 2 3 25000 ? 3 2 1 ? 3 0 12500 ? 0 3 1 ? 0 1 6250 ? 1 0 1 ? 5 4 50000 ? 5 4 1 ? 5 2 25000 ? 2 5 1 ? 2 3 12500 ? 3 2 1 ? 3 0 6250 ? 0 3 1 ? 0 1 3125 ? 1 0 1 ? 6...
result:
ok Correct answer
Test #12:
score: 0
Accepted
time: 62ms
memory: 3556kb
input:
500 FIRST FIRST FIRST FIRST FIRST FIRST SECOND FIRST FIRST FIRST FIRST FIRST SECOND FIRST SECOND FIRST FIRST SECOND SECOND FIRST SECOND FIRST SECOND SECOND FIRST SECOND SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST FIRST SECOND FIRST SECOND SECOND FIRST SECOND FIRST F...
output:
? 1 0 50000 ? 0 1 1 ? 2 1 50000 ? 1 2 1 ? 1 0 25000 ? 0 1 1 ? 3 2 50000 ? 3 2 1 ? 3 1 25000 ? 1 3 1 ? 1 0 12500 ? 0 1 1 ? 4 2 50000 ? 4 2 1 ? 4 3 25000 ? 4 3 1 ? 4 1 12500 ? 1 4 1 ? 5 2 50000 ? 5 2 1 ? 5 3 25000 ? 5 3 1 ? 5 4 12500 ? 5 4 1 ? 5 1 18750 ? 1 5 12501 ? 6 2 50000 ? 6 2 1 ? 6 3 25000 ? 6 ...
result:
ok Correct answer
Test #13:
score: 0
Accepted
time: 95ms
memory: 3516kb
input:
500 FIRST FIRST FIRST FIRST FIRST FIRST SECOND FIRST SECOND FIRST FIRST FIRST SECOND FIRST SECOND FIRST SECOND FIRST FIRST FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST FIRST FIRST SECOND FIRST FIRST FIRST FIRS...
output:
? 1 0 50000 ? 0 1 1 ? 2 1 50000 ? 1 2 1 ? 1 0 25000 ? 0 1 1 ? 3 2 50000 ? 3 2 1 ? 3 1 25000 ? 3 1 1 ? 3 0 12500 ? 0 3 1 ? 4 2 50000 ? 4 2 1 ? 4 1 25000 ? 4 1 1 ? 4 3 12500 ? 4 3 1 ? 4 0 6250 ? 0 4 1 ? 5 2 50000 ? 5 2 1 ? 5 1 25000 ? 5 1 1 ? 5 3 12500 ? 5 3 1 ? 5 4 6250 ? 5 4 1 ? 5 0 3125 ? 5 0 1 ? 6...
result:
ok Correct answer
Test #14:
score: 0
Accepted
time: 130ms
memory: 3620kb
input:
500 FIRST FIRST SECOND FIRST FIRST FIRST SECOND SECOND SECOND FIRST SECOND FIRST FIRST FIRST SECOND FIRST SECOND FIRST SECOND SECOND SECOND FIRST SECOND FIRST SECOND SECOND SECOND FIRST FIRST FIRST SECOND SECOND SECOND FIRST SECOND FIRST SECOND FIRST FIRST FIRST SECOND FIRST SECOND SECOND FIRST SECO...
output:
? 1 0 50000 ? 0 1 1 ? 2 1 50000 ? 2 1 1 ? 2 0 25000 ? 0 2 1 ? 3 1 50000 ? 3 1 1 ? 4 1 50000 ? 4 1 1 ? 4 2 25000 ? 4 2 1 ? 4 0 12500 ? 0 4 1 ? 5 1 50000 ? 5 1 1 ? 5 2 25000 ? 5 2 1 ? 5 4 12500 ? 5 4 1 ? 6 1 50000 ? 6 1 1 ? 6 2 25000 ? 6 2 1 ? 6 4 12500 ? 6 4 1 ? 6 5 18750 ? 6 5 12501 ? 7 1 50000 ? 1 ...
result:
ok Correct answer
Test #15:
score: 0
Accepted
time: 75ms
memory: 3556kb
input:
500 FIRST FIRST FIRST FIRST FIRST FIRST SECOND FIRST SECOND FIRST FIRST FIRST SECOND FIRST SECOND FIRST FIRST FIRST FIRST FIRST SECOND FIRST SECOND FIRST FIRST FIRST FIRST FIRST SECOND SECOND SECOND FIRST SECOND FIRST SECOND FIRST SECOND SECOND SECOND FIRST SECOND FIRST FIRST FIRST SECOND SECOND FIR...
output:
? 1 0 50000 ? 0 1 1 ? 2 1 50000 ? 1 2 1 ? 1 0 25000 ? 0 1 1 ? 3 2 50000 ? 3 2 1 ? 3 1 25000 ? 3 1 1 ? 3 0 12500 ? 0 3 1 ? 4 2 50000 ? 4 2 1 ? 4 1 25000 ? 4 1 1 ? 4 3 12500 ? 3 4 1 ? 3 0 6250 ? 0 3 1 ? 5 2 50000 ? 5 2 1 ? 5 1 25000 ? 5 1 1 ? 5 4 12500 ? 4 5 1 ? 4 3 6250 ? 3 4 1 ? 3 0 3125 ? 3 0 1 ? 6...
result:
ok Correct answer
Test #16:
score: 0
Accepted
time: 77ms
memory: 3616kb
input:
500 FIRST FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND FIRST FIRST FIRST SECOND FIRST SECOND FIRST SECOND FIRST FIRST FIRST SECOND FIRST SECOND FIRST SECOND FIRST FIRST SECOND SECOND FIRST FIRST FIRST FIRST FIRST SECOND SECOND FIRST FIRST SECOND FIRST SECOND FIRST SECOND FIRST SECOND SECOND S...
output:
? 1 0 50000 ? 0 1 1 ? 2 1 50000 ? 2 1 1 ? 2 0 25000 ? 2 0 1 ? 3 1 50000 ? 3 1 1 ? 3 0 25000 ? 3 0 1 ? 3 2 12500 ? 2 3 1 ? 4 1 50000 ? 4 1 1 ? 4 0 25000 ? 4 0 1 ? 4 3 12500 ? 4 3 1 ? 4 2 6250 ? 2 4 1 ? 5 1 50000 ? 5 1 1 ? 5 0 25000 ? 5 0 1 ? 5 3 12500 ? 5 3 1 ? 5 4 6250 ? 4 5 1 ? 6 1 50000 ? 6 1 1 ? ...
result:
ok Correct answer