QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#202778#5531. ICCCamillus61 117ms4180kbC++202.6kb2023-10-06 13:24:012023-10-06 13:24:02

Judging History

你现在查看的是测评时间为 2023-10-06 13:24:02 的历史记录

  • [2024-07-01 04:28:31]
  • 管理员手动重测本题所有提交记录
  • 测评结果:61
  • 用时:112ms
  • 内存:4324kb
  • [2023-10-06 13:24:02]
  • 评测
  • 测评结果:61
  • 用时:117ms
  • 内存:4180kb
  • [2023-10-06 13:24:01]
  • 提交

answer

#include "bits/stdc++.h"
#include "icc.h"
using namespace std;

struct dsu {
    vector<int> p;
    vector<vector<int>> d;

    dsu(int n) {
        p.resize(n);
        d.resize(n);
        for (int i = 0; i < n; i++) {
            p[i] = i;
            d[i] = {i};
        }
    }

    int get(int u) {
        if (u == p[u]) {
            return u;
        } else {
            return p[u] = get(p[u]);
        }
    }

    void join(int u, int v) {
        u = get(u);
        v = get(v);
        if (u == v) {
            return;
        }
        if (d[v].size() > d[u].size()) {
            swap(u, v);
        }
        p[v] = u;
        d[u].insert(d[u].end(), d[v].begin(), d[v].end());
        d[v].clear();
    }
};

random_device rd;
mt19937 rnd(rd());

int rand(int n) {
    return rnd() % n;
}

int rand(int l, int r) {
    return l + rand(r - l + 1);
}

vector<int> low_half(vector<int> A) {
    int x = A.size() >> 1;
    return vector<int>(A.begin(), A.begin() + x);
}

vector<int> top_half(vector<int> A) {
    int x = A.size() >> 1;
    return vector<int>(A.begin() + x, A.end());
}

int query(vector<int> A, vector<int> B) {
    return query(A.size(), B.size(), A.data(), B.data());
}

void run(int n) {
    dsu Q(n + 1);

    auto loop = [&]() {
        vector<int> a;
        vector<int> b;
        while (true) {
            a.clear();
            b.clear();

            for (int u = 1; u <= n; u++) {
                if (Q.get(u) == u && rand(2)) {
                    a.insert(a.end(), Q.d[u].begin(), Q.d[u].end());
                } else {
                    b.insert(b.end(), Q.d[u].begin(), Q.d[u].end());
                }
            }
            if (a.empty() || b.empty()) {
                continue;
            }
            if (query(a, b)) {
                break;
            }
        }

        int c1 = 0, c2 = 0;
        while (b.size() != 1) {
            if (query(a, low_half(b))) {
                b = low_half(b);
            } else {
                b = top_half(b);
            }
            c1++;
        }

        while (a.size() != 1) {
            if (query(low_half(a), b)) {
                a = low_half(a);
            } else {
                a = top_half(a);
            }
            c2++;
        }

        assert(max(c1, c2) <= 7);

        setRoad(a.front(), b.front());
        Q.join(a.front(), b.front());
    };

    for (int i = 0; i < n - 1; i++) {
        loop();
    }
}

#ifdef LOCAL
int main() {
    int n;
    cin >> n;
    run(n);
}
#endif

詳細信息

Subtask #1:

score: 7
Accepted

Test #1:

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

input:

1
1500 3
15

0
2

0.0
2.5

0
3.5

0

1 1

output:

3
Ok! 106 queries used.

result:

points 1.0

Test #2:

score: 0
Accepted
time: 4ms
memory: 3872kb

input:

1
1500 4
15

0
0

0.0
3.5

0
2.5

5

1 1

output:

4
Ok! 103 queries used.

result:

points 1.0

Subtask #2:

score: 11
Accepted

Test #3:

score: 11
Accepted
time: 23ms
memory: 3908kb

input:

1
2500 4
50

0
0

0.0
3.5

0
2.5

5

1 1

output:

4
Ok! 555 queries used.

result:

points 1.0

Test #4:

score: 0
Accepted
time: 36ms
memory: 4128kb

input:

1
2500 4
50

0
1.3

0.0
0.7

0
3.5

15

2 1

output:

4
Ok! 848 queries used.

result:

points 1.0

Test #5:

score: 0
Accepted
time: 35ms
memory: 3984kb

input:

1
2500 3
50

0.05
2.3

0.1
0.7

0
1.5

1.7

2 1

output:

3
Ok! 830 queries used.

result:

points 1.0

Subtask #3:

score: 22
Accepted

Test #6:

score: 22
Accepted
time: 82ms
memory: 4008kb

input:

1
2250 6
100

0.05
2.3

0.1
0.7

0
1.5

1.7

1.1 1

output:

6
Ok! 1570 queries used.

result:

points 1.0

Test #7:

score: 0
Accepted
time: 117ms
memory: 3940kb

input:

1
2250 6
100

0.05
1.5

0.1
1.3

0.01
1.7

0

100 1

output:

6
Ok! 2174 queries used.

result:

points 1.0

Test #8:

score: 0
Accepted
time: 88ms
memory: 4088kb

input:

1
2250 5
100

0.00
2.00

0.00
1.70

0.10
1.30

5

1.15 1

output:

5
Ok! 1747 queries used.

result:

points 1.0

Test #9:

score: 0
Accepted
time: 92ms
memory: 4164kb

input:

1
2250 5
100

0.00
1.00

0.00
2.30

0.00
0.70

0

1.1 1

output:

5
Ok! 1732 queries used.

result:

points 1.0

Subtask #4:

score: 21
Accepted

Test #10:

score: 21
Accepted
time: 87ms
memory: 4160kb

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

result:

points 1.0

Test #11:

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

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

result:

points 1.0

Test #12:

score: 0
Accepted
time: 87ms
memory: 4152kb

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

result:

points 1.0

Test #13:

score: 0
Accepted
time: 91ms
memory: 4152kb

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

result:

points 1.0

Subtask #5:

score: 0
Acceptable Answer

Test #14:

score: 0
Acceptable Answer
time: 99ms
memory: 4152kb

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

result:

points inf0

Subtask #6:

score: 0
Acceptable Answer

Test #20:

score: 0
Acceptable Answer
time: 111ms
memory: 4148kb

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