QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#380393 | #5531. ICC | nhuang685# | 61 | 110ms | 4348kb | C++20 | 3.9kb | 2024-04-07 02:48:22 | 2024-04-07 02:48:23 |
Judging History
answer
#include <bits/stdc++.h>
#ifndef LOCAL
#include "icc.h"
#endif
std::vector<std::vector<int>> gr;
std::vector<int> par;
std::vector<int> nodes;
// std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
std::mt19937 rng(2);
int find(int a) {
return par[a] < 0 ? a : par[a] = find(par[a]);
}
#ifdef LOCAL
namespace iv {
std::array<std::array<bool, 101>, 101> cc;
int na = -1, nb = -1;
int cnt = 0;
int num = 0;
int n;
} // namespace iv
int query(int a, int b, int *A, int *B) {
++iv::cnt;
for (int ii = 0; ii < a; ++ii) {
int i = A[ii];
for (int jj = 0; jj < b; ++jj) {
int j = B[jj];
if (iv::cc[i][j]) {
return true;
}
}
}
return false;
}
bool connected(int a, int b) {
if (a == b) {
return true;
}
if (par.empty()) {
return false;
}
a = find(a);
b = find(b);
return a == b;
}
void newQuery() {
while (true) {
int a = (int)(rng() % iv::n + 1);
int b = (int)(rng() % iv::n + 1);
if (!connected(a, b)) {
if (a > b) {
std::swap(a, b);
}
iv::na = a;
iv::nb = b;
iv::cc[a][b] = true;
iv::cc[b][a] = true;
return;
}
}
}
void setRoad(int a, int b) {
if (a > b) {
std::swap(a, b);
}
++iv::num;
std::cerr << "Query " << iv::num << ":" << std::endl;
std::cerr << "Your answer is: " << a << ' ' << b << std::endl;
std::cerr << "The correct answer is: " << iv::na << ' ' << iv::nb
<< std::endl;
std::cerr << std::endl;
if (iv::na != a || iv::nb != b) {
std::cerr << "Wrong Answer" << std::endl;
std::exit(0);
}
if (iv::num < iv::n - 1) {
newQuery();
}
}
#endif
bool query(std::vector<int> &a, std::vector<int> &b) {
if (a.empty() || b.empty()) {
return false;
}
return query((int)a.size(), (int)b.size(), a.data(), b.data());
}
void unite(int a, int b) {
int aa = a, bb = b;
a = find(a);
b = find(b);
if (par[a] > par[b]) {
std::swap(a, b);
}
gr[a].insert(gr[a].end(), gr[b].begin(), gr[b].end());
gr[b].clear();
par[a] += par[b];
par[b] = a;
setRoad(aa, bb);
}
void run(int N) {
const int n = N;
gr.resize(n + 1);
for (int i = 1; i <= n; ++i) {
gr[i].push_back(i);
}
nodes.resize(n);
par.resize(n + 1, -1);
std::iota(nodes.begin(), nodes.end(), 1);
for (int i = 0; i < n - 1; ++i) {
std::vector<int> a, b;
while (true) {
a.clear();
b.clear();
std::shuffle(nodes.begin(), nodes.end(), rng);
for (int j = 0; j < n / 2; ++j) {
a.insert(a.end(), gr[nodes[j]].begin(), gr[nodes[j]].end());
}
for (int j = n / 2; j < n; ++j) {
b.insert(b.end(), gr[nodes[j]].begin(), gr[nodes[j]].end());
}
if (query(a, b)) {
break;
}
}
while ((int)a.size() > 1) {
std::vector<int> na1(a.begin(), a.begin() + a.size() / 2),
na2(a.begin() + a.size() / 2, a.end());
if (query(na1, b)) {
a = na1;
} else {
a = na2;
}
}
while ((int)b.size() > 1) {
std::vector<int> nb1(b.begin(), b.begin() + b.size() / 2),
nb2(b.begin() + b.size() / 2, b.end());
if (query(nb1, a)) {
b = nb1;
} else {
b = nb2;
}
}
unite(a[0], b[0]);
}
}
#ifdef LOCAL
int main() {
int n;
std::cin >> n;
iv::n = n;
newQuery();
run(n);
std::cerr << "Number of queries used: " << iv::cnt << '\n';
}
#endif
详细
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 5ms
memory: 4092kb
input:
1 1500 3 15 0 2 0.0 2.5 0 3.5 0 1 1
output:
3 Ok! 111 queries used.
result:
points 1.0
Test #2:
score: 0
Accepted
time: 5ms
memory: 4312kb
input:
1 1500 4 15 0 0 0.0 3.5 0 2.5 5 1 1
output:
4 Ok! 105 queries used.
result:
points 1.0
Subtask #2:
score: 11
Accepted
Test #3:
score: 11
Accepted
time: 18ms
memory: 4324kb
input:
1 2500 4 50 0 0 0.0 3.5 0 2.5 5 1 1
output:
4 Ok! 552 queries used.
result:
points 1.0
Test #4:
score: 0
Accepted
time: 30ms
memory: 4176kb
input:
1 2500 4 50 0 1.3 0.0 0.7 0 3.5 15 2 1
output:
4 Ok! 854 queries used.
result:
points 1.0
Test #5:
score: 0
Accepted
time: 30ms
memory: 4164kb
input:
1 2500 3 50 0.05 2.3 0.1 0.7 0 1.5 1.7 2 1
output:
3 Ok! 836 queries used.
result:
points 1.0
Subtask #3:
score: 22
Accepted
Test #6:
score: 22
Accepted
time: 76ms
memory: 4244kb
input:
1 2250 6 100 0.05 2.3 0.1 0.7 0 1.5 1.7 1.1 1
output:
6 Ok! 1539 queries used.
result:
points 1.0
Test #7:
score: 0
Accepted
time: 110ms
memory: 4192kb
input:
1 2250 6 100 0.05 1.5 0.1 1.3 0.01 1.7 0 100 1
output:
6 Ok! 2137 queries used.
result:
points 1.0
Test #8:
score: 0
Accepted
time: 87ms
memory: 4280kb
input:
1 2250 5 100 0.00 2.00 0.00 1.70 0.10 1.30 5 1.15 1
output:
5 Ok! 1714 queries used.
result:
points 1.0
Test #9:
score: 0
Accepted
time: 86ms
memory: 4268kb
input:
1 2250 5 100 0.00 1.00 0.00 2.30 0.00 0.70 0 1.1 1
output:
5 Ok! 1727 queries used.
result:
points 1.0
Subtask #4:
score: 21
Accepted
Test #10:
score: 21
Accepted
time: 75ms
memory: 4336kb
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! 1567 queries used.
result:
points 1.0
Test #11:
score: 0
Accepted
time: 95ms
memory: 4280kb
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! 1897 queries used.
result:
points 1.0
Test #12:
score: 0
Accepted
time: 78ms
memory: 4348kb
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! 1560 queries used.
result:
points 1.0
Test #13:
score: 0
Accepted
time: 78ms
memory: 4256kb
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! 1620 queries used.
result:
points 1.0
Subtask #5:
score: 0
Acceptable Answer
Test #14:
score: 0
Acceptable Answer
time: 94ms
memory: 4192kb
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! 1822 out of 1775
result:
points inf0
Subtask #6:
score: 0
Acceptable Answer
Test #20:
score: 0
Acceptable Answer
time: 106ms
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! 2078 out of 1625
result:
points inf0