QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#202761 | #5531. ICC | Camillus | 18 | 36ms | 4244kb | C++20 | 2.6kb | 2023-10-06 13:20:52 | 2023-10-06 13:20:53 |
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) <= 6);
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: 4104kb
input:
1 1500 3 15 0 2 0.0 2.5 0 3.5 0 1 1
output:
3 Ok! 103 queries used.
result:
points 1.0
Test #2:
score: 0
Accepted
time: 4ms
memory: 4120kb
input:
1 1500 4 15 0 0 0.0 3.5 0 2.5 5 1 1
output:
4 Ok! 104 queries used.
result:
points 1.0
Subtask #2:
score: 11
Accepted
Test #3:
score: 11
Accepted
time: 22ms
memory: 4240kb
input:
1 2500 4 50 0 0 0.0 3.5 0 2.5 5 1 1
output:
4 Ok! 548 queries used.
result:
points 1.0
Test #4:
score: 0
Accepted
time: 36ms
memory: 4244kb
input:
1 2500 4 50 0 1.3 0.0 0.7 0 3.5 15 2 1
output:
4 Ok! 864 queries used.
result:
points 1.0
Test #5:
score: 0
Accepted
time: 34ms
memory: 4156kb
input:
1 2500 3 50 0.05 2.3 0.1 0.7 0 1.5 1.7 2 1
output:
3 Ok! 833 queries used.
result:
points 1.0
Subtask #3:
score: 0
Runtime Error
Test #6:
score: 0
Runtime Error
input:
1 2250 6 100 0.05 2.3 0.1 0.7 0 1.5 1.7 1.1 1
output:
Unauthorized output
result:
Subtask #4:
score: 0
Runtime Error
Test #10:
score: 0
Runtime Error
input:
1 2000 5 100 0.01 1.00 0.10 1.70 0.00 1.50 5.0 1.20 1
output:
Unauthorized output
result:
Subtask #5:
score: 0
Runtime Error
Test #14:
score: 0
Runtime Error
input:
1 1775 4 100 0.00 0.00 0.00 2.70 0.10 7.55 0.0 1.15 1
output:
Unauthorized output
result:
Subtask #6:
score: 0
Runtime Error
Test #20:
score: 0
Runtime Error
input:
1 1625 5 100 0.00 0.00 0.00 3.00 0.00 1.00 0.0 3 1
output:
Unauthorized output