QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#380373 | #5531. ICC | nhuang685# | 0 | 2ms | 4304kb | C++20 | 2.9kb | 2024-04-07 02:12:50 | 2024-04-07 02:12:51 |
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> nodes;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
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 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);
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;
}
}
setRoad(a[0], b[0]);
gr[a[0]].insert(gr[a[0]].end(), gr[b[0]].begin(), gr[b[0]].end());
gr[b[0]].clear();
}
#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
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Acceptable Answer
Test #1:
score: 0
Acceptable Answer
time: 1ms
memory: 4304kb
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: 0ms
memory: 4244kb
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: 4240kb
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: 4264kb
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: 4248kb
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: 4124kb
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