QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380382#5531. ICCnhuang685#61 102ms4296kbC++203.6kb2024-04-07 02:33:412024-04-07 02:33:42

Judging History

你现在查看的是测评时间为 2024-04-07 02:33:42 的历史记录

  • [2024-07-01 04:28:48]
  • 管理员手动重测本题所有提交记录
  • 测评结果:61
  • 用时:104ms
  • 内存:4356kb
  • [2024-04-07 02:33:42]
  • 评测
  • 测评结果:61
  • 用时:102ms
  • 内存:4296kb
  • [2024-04-07 02:33:41]
  • 提交

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;
    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 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
// bool connected(int a, int b) {
//     if (a == b) {
//         return true;
//     }
//     if (par.empty()) {
//         return false;
//     }
//     while (par[a] != -1) {
//         a = par[a];
//     }
//     while (par[b] != -1) {
//         b = par[b];
//     }
//     return a == b;
// }
// void reset() {
//     auto seed = std::chrono::steady_clock::now().time_since_epoch().count();
//     std::cerr << seed << '\n';
//     gr.clear();
//     par.clear();
//     nodes.clear();
//     for (auto &a : iv::cc) {
//         a.fill(false);
//     }
//     iv::na = -1;
//     iv::nb = -1;
//     iv::cnt = 0;
// }
// int main() {
//     int n;
//     std::cin >> n;

// }
// #endif

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 4ms
memory: 4200kb

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: 4152kb

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: 19ms
memory: 4208kb

input:

1
2500 4
50

0
0

0.0
3.5

0
2.5

5

1 1

output:

4
Ok! 541 queries used.

result:

points 1.0

Test #4:

score: 0
Accepted
time: 31ms
memory: 4200kb

input:

1
2500 4
50

0
1.3

0.0
0.7

0
3.5

15

2 1

output:

4
Ok! 830 queries used.

result:

points 1.0

Test #5:

score: 0
Accepted
time: 26ms
memory: 4272kb

input:

1
2500 3
50

0.05
2.3

0.1
0.7

0
1.5

1.7

2 1

output:

3
Ok! 823 queries used.

result:

points 1.0

Subtask #3:

score: 22
Accepted

Test #6:

score: 22
Accepted
time: 71ms
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! 1553 queries used.

result:

points 1.0

Test #7:

score: 0
Accepted
time: 102ms
memory: 4220kb

input:

1
2250 6
100

0.05
1.5

0.1
1.3

0.01
1.7

0

100 1

output:

6
Ok! 2155 queries used.

result:

points 1.0

Test #8:

score: 0
Accepted
time: 82ms
memory: 4252kb

input:

1
2250 5
100

0.00
2.00

0.00
1.70

0.10
1.30

5

1.15 1

output:

5
Ok! 1770 queries used.

result:

points 1.0

Test #9:

score: 0
Accepted
time: 76ms
memory: 4256kb

input:

1
2250 5
100

0.00
1.00

0.00
2.30

0.00
0.70

0

1.1 1

output:

5
Ok! 1688 queries used.

result:

points 1.0

Subtask #4:

score: 21
Accepted

Test #10:

score: 21
Accepted
time: 73ms
memory: 4192kb

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! 1579 queries used.

result:

points 1.0

Test #11:

score: 0
Accepted
time: 84ms
memory: 4292kb

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! 1840 queries used.

result:

points 1.0

Test #12:

score: 0
Accepted
time: 71ms
memory: 4296kb

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! 1532 queries used.

result:

points 1.0

Test #13:

score: 0
Accepted
time: 79ms
memory: 4168kb

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! 1652 queries used.

result:

points 1.0

Subtask #5:

score: 0
Acceptable Answer

Test #14:

score: 0
Acceptable Answer
time: 87ms
memory: 4236kb

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! 1842 out of 1775

result:

points inf0

Subtask #6:

score: 0
Acceptable Answer

Test #20:

score: 0
Acceptable Answer
time: 96ms
memory: 4296kb

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! 2054 out of 1625

result:

points inf0