QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#202765 | #5531. ICC | Camillus | 61 | 113ms | 4284kb | C++20 | 2.6kb | 2023-10-06 13:21:19 | 2023-10-06 13:21:19 |
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();
}
};
random_device rd;
mt19937 rnd(rd());
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) {
int x = A.size() >> 1;
return vector<int>(A.begin(), A.begin() + x);
}
vector<int> top_half(vector<int> 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;
}
}
int c1 = 0, c2 = 0;
while (b.size() != 1) {
if (query(a, low_half(b))) {
b = low_half(b);
} else {
b = top_half(b);
}
c1++;
}
while (a.size() != 1) {
if (query(low_half(a), b)) {
a = low_half(a);
} else {
a = top_half(a);
}
c2++;
}
assert(max(c1, c2) <= 7);
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: 4ms
memory: 4084kb
input:
1 1500 3 15 0 2 0.0 2.5 0 3.5 0 1 1
output:
3 Ok! 105 queries used.
result:
points 1.0
Test #2:
score: 0
Accepted
time: 4ms
memory: 4064kb
input:
1 1500 4 15 0 0 0.0 3.5 0 2.5 5 1 1
output:
4 Ok! 106 queries used.
result:
points 1.0
Subtask #2:
score: 11
Accepted
Test #3:
score: 11
Accepted
time: 23ms
memory: 4220kb
input:
1 2500 4 50 0 0 0.0 3.5 0 2.5 5 1 1
output:
4 Ok! 561 queries used.
result:
points 1.0
Test #4:
score: 0
Accepted
time: 36ms
memory: 4124kb
input:
1 2500 4 50 0 1.3 0.0 0.7 0 3.5 15 2 1
output:
4 Ok! 847 queries used.
result:
points 1.0
Test #5:
score: 0
Accepted
time: 35ms
memory: 4076kb
input:
1 2500 3 50 0.05 2.3 0.1 0.7 0 1.5 1.7 2 1
output:
3 Ok! 846 queries used.
result:
points 1.0
Subtask #3:
score: 22
Accepted
Test #6:
score: 22
Accepted
time: 76ms
memory: 4096kb
input:
1 2250 6 100 0.05 2.3 0.1 0.7 0 1.5 1.7 1.1 1
output:
6 Ok! 1532 queries used.
result:
points 1.0
Test #7:
score: 0
Accepted
time: 113ms
memory: 4208kb
input:
1 2250 6 100 0.05 1.5 0.1 1.3 0.01 1.7 0 100 1
output:
6 Ok! 2169 queries used.
result:
points 1.0
Test #8:
score: 0
Accepted
time: 90ms
memory: 4160kb
input:
1 2250 5 100 0.00 2.00 0.00 1.70 0.10 1.30 5 1.15 1
output:
5 Ok! 1722 queries used.
result:
points 1.0
Test #9:
score: 0
Accepted
time: 90ms
memory: 4100kb
input:
1 2250 5 100 0.00 1.00 0.00 2.30 0.00 0.70 0 1.1 1
output:
5 Ok! 1713 queries used.
result:
points 1.0
Subtask #4:
score: 21
Accepted
Test #10:
score: 21
Accepted
time: 87ms
memory: 4284kb
input:
1 2000 5 100 0.01 1.00 0.10 1.70 0.00 1.50 5.0 1.20 1
output:
5 Ok! 1658 queries used.
result:
points 1.0
Test #11:
score: 0
Accepted
time: 98ms
memory: 4164kb
input:
1 2000 5 100 0.00 0.70 0.00 2.10 0.00 1.20 0.0 1.5 1
output:
5 Ok! 1847 queries used.
result:
points 1.0
Test #12:
score: 0
Accepted
time: 84ms
memory: 4160kb
input:
1 2000 6 100 0.01 0.70 0.00 2.70 0.00 1.90 3.5 1.1 1
output:
6 Ok! 1610 queries used.
result:
points 1.0
Test #13:
score: 0
Accepted
time: 91ms
memory: 4144kb
input:
1 2000 5 100 0.01 1.00 0.10 1.70 0.01 2.30 5.0 1.20 1
output:
5 Ok! 1723 queries used.
result:
points 1.0
Subtask #5:
score: 0
Acceptable Answer
Test #14:
score: 0
Acceptable Answer
time: 97ms
memory: 4208kb
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! 1828 out of 1775
result:
points inf0
Subtask #6:
score: 0
Acceptable Answer
Test #20:
score: 0
Acceptable Answer
time: 101ms
memory: 4192kb
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! 1895 out of 1625
result:
points inf0