QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#380375 | #5531. ICC | nhuang685# | 0 | 2ms | 4276kb | C++20 | 3.2kb | 2024-04-07 02:19:30 | 2024-04-07 02:19:31 |
Judging History
answer
#include <bits/stdc++.h>
#ifndef LOCAL
#include "icc.h"
#else
namespace iv {
std::array<std::array<bool, 101>, 101> cc;
int na = -1, nb = -1;
int cnt = 0;
} // 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;
}
void setRoad(int a, int b) {
if (a > b) {
std::swap(a, b);
}
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);
}
}
#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);
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) {
setRoad(a, b);
while (par[a] != -1) {
a = par[a];
}
while (par[b] != -1) {
b = par[b];
}
gr[a].insert(gr[a].end(), gr[b].begin(), gr[b].end());
gr[b].clear();
par[b] = a;
}
void run(int N) {
const int n = N;
if (gr.empty()) {
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);
}
std::vector<int> a, b;
while (true) {
a.clear();
b.clear();
std::shuffle(nodes.begin(), nodes.end(), rng);
for (int i = 0; i < n / 2; ++i) {
a.insert(a.end(), gr[nodes[i]].begin(), gr[nodes[i]].end());
}
for (int i = n / 2; i < n; ++i) {
b.insert(b.end(), gr[nodes[i]].begin(), gr[nodes[i]].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;
for (int i = 0; i < n - 1; ++i) {
std::cin >> iv::na >> iv::nb;
if (iv::na > iv::nb) {
std::swap(iv::na, iv::nb);
}
iv::cc[iv::na][iv::nb] = true;
iv::cc[iv::nb][iv::na] = true;
run(n);
}
std::cerr << "Number of queries used: " << iv::cnt << std::endl;
}
#endif
詳細信息
Subtask #1:
score: 0
Acceptable Answer
Test #1:
score: 0
Acceptable Answer
time: 1ms
memory: 4132kb
input:
1 1500 3 15 0 2 0.0 2.5 0 3.5 0 1 1
output:
0 Not all edges were guessed!
result:
points inf0
Subtask #2:
score: 0
Acceptable Answer
Test #3:
score: 0
Acceptable Answer
time: 1ms
memory: 4216kb
input:
1 2500 4 50 0 0 0.0 3.5 0 2.5 5 1 1
output:
0 Not all edges were guessed!
result:
points inf0
Subtask #3:
score: 0
Acceptable Answer
Test #6:
score: 0
Acceptable Answer
time: 2ms
memory: 4276kb
input:
1 2250 6 100 0.05 2.3 0.1 0.7 0 1.5 1.7 1.1 1
output:
0 Not all edges were guessed!
result:
points inf0
Subtask #4:
score: 0
Acceptable Answer
Test #10:
score: 0
Acceptable Answer
time: 2ms
memory: 4272kb
input:
1 2000 5 100 0.01 1.00 0.10 1.70 0.00 1.50 5.0 1.20 1
output:
0 Not all edges were guessed!
result:
points inf0
Subtask #5:
score: 0
Acceptable Answer
Test #14:
score: 0
Acceptable Answer
time: 2ms
memory: 4224kb
input:
1 1775 4 100 0.00 0.00 0.00 2.70 0.10 7.55 0.0 1.15 1
output:
0 Not all edges were guessed!
result:
points inf0
Subtask #6:
score: 0
Acceptable Answer
Test #20:
score: 0
Acceptable Answer
time: 2ms
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 Not all edges were guessed!
result:
points inf0