QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#384625 | #5531. ICC | nhuang685 | 90 | 78ms | 4308kb | C++20 | 4.3kb | 2024-04-10 07:46:22 | 2024-04-10 07:46: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, b;
// a = iv::num + 1;
// b = iv::num + 2;
if (iv::num == 0) {
a = (int)(rng() % iv::n) + 1;
b = (int)(rng() % iv::n) + 1;
} else {
int aa = (int)(rng() % iv::n) + 1;
if (gr[aa].empty()) {
continue;
}
a = gr[aa][rng() % gr[aa].size()];
int bb = (int)(rng() % iv::n) + 1;
if (gr[bb].empty()) {
continue;
}
b = gr[bb][rng() % gr[bb].size()];
}
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());
}
bool queryG(std::vector<int> &ag, std::vector<int> &bg) {
std::vector<int> a, b;
for (int i : ag) {
a.insert(a.end(), gr[i].begin(), gr[i].end());
}
for (int i : bg) {
b.insert(b.end(), gr[i].begin(), gr[i].end());
}
return query(a, b);
}
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);
}
const int LG = 7;
void run(int N) {
const int n = N;
gr.resize(n + 1);
for (int i = 1; i <= n; ++i) {
gr[i].push_back(i);
}
par.resize(n + 1, -1);
for (int i = 0; i < n - 1; ++i) {
// std::vector<int> a, b;
std::vector<int> seq(LG);
std::iota(seq.begin(), seq.end(), 0);
std::shuffle(seq.begin(), seq.end(), rng);
std::vector<int> a, b;
nodes.clear();
for (int j = 1; j <= n; ++j) {
if (!gr[j].empty()) {
nodes.push_back(j);
}
}
for (int j : seq) {
a.clear();
b.clear();
for (int k : nodes) {
if ((1 << j) & k) {
a.insert(a.end(), gr[k].begin(), gr[k].end());
} else {
b.insert(b.end(), gr[k].begin(), gr[k].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: 4ms
memory: 4212kb
input:
1 1500 3 15 0 2 0.0 2.5 0 3.5 0 1 1
output:
3 Ok! 98 queries used.
result:
points 1.0
Test #2:
score: 0
Accepted
time: 4ms
memory: 4212kb
input:
1 1500 4 15 0 0 0.0 3.5 0 2.5 5 1 1
output:
4 Ok! 100 queries used.
result:
points 1.0
Subtask #2:
score: 11
Accepted
Test #3:
score: 11
Accepted
time: 19ms
memory: 4300kb
input:
1 2500 4 50 0 0 0.0 3.5 0 2.5 5 1 1
output:
4 Ok! 558 queries used.
result:
points 1.0
Test #4:
score: 0
Accepted
time: 25ms
memory: 4172kb
input:
1 2500 4 50 0 1.3 0.0 0.7 0 3.5 15 2 1
output:
4 Ok! 714 queries used.
result:
points 1.0
Test #5:
score: 0
Accepted
time: 21ms
memory: 4300kb
input:
1 2500 3 50 0.05 2.3 0.1 0.7 0 1.5 1.7 2 1
output:
3 Ok! 690 queries used.
result:
points 1.0
Subtask #3:
score: 22
Accepted
Test #6:
score: 22
Accepted
time: 60ms
memory: 4228kb
input:
1 2250 6 100 0.05 2.3 0.1 0.7 0 1.5 1.7 1.1 1
output:
6 Ok! 1402 queries used.
result:
points 1.0
Test #7:
score: 0
Accepted
time: 78ms
memory: 4228kb
input:
1 2250 6 100 0.05 1.5 0.1 1.3 0.01 1.7 0 100 1
output:
6 Ok! 1776 queries used.
result:
points 1.0
Test #8:
score: 0
Accepted
time: 69ms
memory: 4180kb
input:
1 2250 5 100 0.00 2.00 0.00 1.70 0.10 1.30 5 1.15 1
output:
5 Ok! 1571 queries used.
result:
points 1.0
Test #9:
score: 0
Accepted
time: 64ms
memory: 4172kb
input:
1 2250 5 100 0.00 1.00 0.00 2.30 0.00 0.70 0 1.1 1
output:
5 Ok! 1494 queries used.
result:
points 1.0
Subtask #4:
score: 21
Accepted
Test #10:
score: 21
Accepted
time: 65ms
memory: 4308kb
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! 1521 queries used.
result:
points 1.0
Test #11:
score: 0
Accepted
time: 71ms
memory: 4244kb
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! 1629 queries used.
result:
points 1.0
Test #12:
score: 0
Accepted
time: 57ms
memory: 4240kb
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! 1436 queries used.
result:
points 1.0
Test #13:
score: 0
Accepted
time: 64ms
memory: 4228kb
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! 1499 queries used.
result:
points 1.0
Subtask #5:
score: 29
Accepted
Test #14:
score: 29
Accepted
time: 74ms
memory: 4164kb
input:
1 1775 4 100 0.00 0.00 0.00 2.70 0.10 7.55 0.0 1.15 1
output:
4 Ok! 1663 queries used.
result:
points 1.0
Test #15:
score: 0
Accepted
time: 77ms
memory: 4228kb
input:
1 1775 5 100 0.00 1.50 0.00 1.10 0.00 1.75 0.0 1.5 1
output:
5 Ok! 1742 queries used.
result:
points 1.0
Test #16:
score: 0
Accepted
time: 67ms
memory: 4256kb
input:
1 1775 5 100 0.01 1.50 0.00 1.10 0.01 1.75 0.0 1.3 1
output:
5 Ok! 1624 queries used.
result:
points 1.0
Test #17:
score: 0
Accepted
time: 70ms
memory: 4220kb
input:
1 1775 5 100 0.00 0.30 0.00 2.10 0.00 1.75 0.0 1.5 1
output:
5 Ok! 1638 queries used.
result:
points 1.0
Test #18:
score: 0
Accepted
time: 67ms
memory: 4244kb
input:
1 1775 5 100 0.01 0.70 0.00 2.70 0.00 1.90 3.5 1.5 1
output:
5 Ok! 1639 queries used.
result:
points 1.0
Test #19:
score: 0
Accepted
time: 61ms
memory: 4180kb
input:
1 1775 5 100 0.01 1.50 0.00 1.10 0.01 1.75 1.0 1.10 1
output:
5 Ok! 1498 queries used.
result:
points 1.0
Subtask #6:
score: 0
Acceptable Answer
Test #20:
score: 0
Acceptable Answer
time: 78ms
memory: 4240kb
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! 1757 out of 1625
result:
points inf0