QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#202721 | #5531. ICC | Camillus | 0 | 3ms | 4268kb | C++20 | 2.7kb | 2023-10-06 13:11:56 | 2023-10-06 13:11:57 |
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());
};
for (int i = 0; i < n - 1; i++) {
loop();
}
}
#ifdef LOCAL
int main() {
int n;
cin >> n;
run(n);
}
#endif
詳細信息
Subtask #1:
score: 0
Acceptable Answer
Test #1:
score: 0
Acceptable Answer
time: 1ms
memory: 4264kb
input:
1 1500 3 15 0 2 0.0 2.5 0 3.5 0 1 1
output:
0 Wrong road!
result:
points inf0
Subtask #2:
score: 0
Acceptable Answer
Test #3:
score: 0
Acceptable Answer
time: 0ms
memory: 4176kb
input:
1 2500 4 50 0 0 0.0 3.5 0 2.5 5 1 1
output:
0 Wrong road!
result:
points inf0
Subtask #3:
score: 0
Acceptable Answer
Test #6:
score: 0
Acceptable Answer
time: 3ms
memory: 4268kb
input:
1 2250 6 100 0.05 2.3 0.1 0.7 0 1.5 1.7 1.1 1
output:
0 Wrong road!
result:
points inf0
Subtask #4:
score: 0
Acceptable Answer
Test #10:
score: 0
Acceptable Answer
time: 2ms
memory: 4216kb
input:
1 2000 5 100 0.01 1.00 0.10 1.70 0.00 1.50 5.0 1.20 1
output:
0 Wrong road!
result:
points inf0
Subtask #5:
score: 0
Acceptable Answer
Test #14:
score: 0
Acceptable Answer
time: 3ms
memory: 4180kb
input:
1 1775 4 100 0.00 0.00 0.00 2.70 0.10 7.55 0.0 1.15 1
output:
0 Wrong road!
result:
points inf0
Subtask #6:
score: 0
Acceptable Answer
Test #20:
score: 0
Acceptable Answer
time: 0ms
memory: 4180kb
input:
1 1625 5 100 0.00 0.00 0.00 3.00 0.00 1.00 0.0 3 1
output:
0 Wrong road!
result:
points inf0