QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#202732 | #5531. ICC | Camillus | 18 | 129ms | 4312kb | C++20 | 2.8kb | 2023-10-06 13:13:30 | 2023-10-06 13:13:30 |
Judging History
answer
#include "bits/stdc++.h"
#include "icc.h"
using namespace std;
struct dsu {
vector<int> p;
vector<vector<int>> d;
dsu(int n) {
p.resize(n);
d.resize(n);
for (int i = 0; i < n; i++) {
p[i] = i;
d[i] = {i};
}
}
int get(int u) {
if (u == p[u]) {
return u;
} else {
return p[u] = get(p[u]);
}
}
void join(int u, int v) {
u = get(u);
v = get(v);
if (u == v) {
return;
}
if (d[v].size() > d[u].size()) {
swap(u, v);
}
p[v] = u;
d[u].insert(d[u].end(), d[v].begin(), d[v].end());
d[v].clear();
}
};
mt19937 rnd(228);
int rand(int n) {
return rnd() % n;
}
int rand(int l, int r) {
return l + rand(r - l + 1);
}
vector<int> low_half(vector<int> A) {
if (A.size() == 1) {
return A;
}
int x = A.size() >> 1;
return vector<int>(A.begin(), A.begin() + x);
}
vector<int> top_half(vector<int> A) {
if (A.size() == 1) {
return A;
}
int x = A.size() >> 1;
return vector<int>(A.begin() + x, A.end());
}
int query(vector<int> A, vector<int> B) {
return query(A.size(), B.size(), A.data(), B.data());
}
void run(int n) {
dsu Q(n + 1);
auto loop = [&]() {
vector<int> a;
vector<int> b;
while (true) {
a.clear();
b.clear();
for (int u = 1; u <= n; u++) {
if (Q.get(u) == u && rand(2)) {
a.insert(a.end(), Q.d[u].begin(), Q.d[u].end());
} else {
b.insert(b.end(), Q.d[u].begin(), Q.d[u].end());
}
}
if (a.empty() || b.empty()) {
continue;
}
if (query(a, b)) {
break;
}
}
while (a.size() != 1 || b.size() != 1) {
if (query(low_half(a), low_half(b))) {
a = low_half(a);
b = low_half(b);
}
else if (query(low_half(a), top_half(b))) {
a = low_half(a);
b = top_half(b);
}
else if (query(top_half(a), low_half(b))) {
a = top_half(a);
b = low_half(b);
}
else {
a = top_half(a);
b = top_half(b);
}
}
setRoad(a.front(), b.front());
Q.join(a.front(), b.front());
};
for (int i = 0; i < n - 1; i++) {
loop();
}
}
#ifdef LOCAL
int main() {
int n;
cin >> n;
run(n);
}
#endif
详细
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 3ms
memory: 4292kb
input:
1 1500 3 15 0 2 0.0 2.5 0 3.5 0 1 1
output:
3 Ok! 169 queries used.
result:
points 1.0
Test #2:
score: 0
Accepted
time: 6ms
memory: 4164kb
input:
1 1500 4 15 0 0 0.0 3.5 0 2.5 5 1 1
output:
4 Ok! 153 queries used.
result:
points 1.0
Subtask #2:
score: 11
Accepted
Test #3:
score: 11
Accepted
time: 33ms
memory: 4312kb
input:
1 2500 4 50 0 0 0.0 3.5 0 2.5 5 1 1
output:
4 Ok! 803 queries used.
result:
points 1.0
Test #4:
score: 0
Accepted
time: 42ms
memory: 4160kb
input:
1 2500 4 50 0 1.3 0.0 0.7 0 3.5 15 2 1
output:
4 Ok! 1025 queries used.
result:
points 1.0
Test #5:
score: 0
Accepted
time: 39ms
memory: 4260kb
input:
1 2500 3 50 0.05 2.3 0.1 0.7 0 1.5 1.7 2 1
output:
3 Ok! 975 queries used.
result:
points 1.0
Subtask #3:
score: 0
Acceptable Answer
Test #6:
score: 22
Accepted
time: 106ms
memory: 4132kb
input:
1 2250 6 100 0.05 2.3 0.1 0.7 0 1.5 1.7 1.1 1
output:
6 Ok! 2199 queries used.
result:
points 1.0
Test #7:
score: -22
Acceptable Answer
time: 129ms
memory: 4244kb
input:
1 2250 6 100 0.05 1.5 0.1 1.3 0.01 1.7 0 100 1
output:
0 Too many queries! 2439 out of 2250
result:
points inf0
Subtask #4:
score: 0
Acceptable Answer
Test #10:
score: 0
Acceptable Answer
time: 113ms
memory: 4136kb
input:
1 2000 5 100 0.01 1.00 0.10 1.70 0.00 1.50 5.0 1.20 1
output:
0 Too many queries! 2220 out of 2000
result:
points inf0
Subtask #5:
score: 0
Acceptable Answer
Test #14:
score: 0
Acceptable Answer
time: 116ms
memory: 4184kb
input:
1 1775 4 100 0.00 0.00 0.00 2.70 0.10 7.55 0.0 1.15 1
output:
0 Too many queries! 2267 out of 1775
result:
points inf0
Subtask #6:
score: 0
Acceptable Answer
Test #20:
score: 0
Acceptable Answer
time: 125ms
memory: 4200kb
input:
1 1625 5 100 0.00 0.00 0.00 3.00 0.00 1.00 0.0 3 1
output:
0 Too many queries! 2410 out of 1625
result:
points inf0