oj.uz

Submission #372449

# Submission time Handle Problem Language Result Execution time Memory
372449 2021-02-28T08:36:32 Z KoD Chameleon's Love (JOI20_chameleon) C++17
40 / 100
 33 ms 492 KB 
#include <bits/stdc++.h>
#include "chameleon.h"

template <class T>
using Vec = std::vector<T>;

void Solve(int N) {
    Vec<Vec<int>> graph(2 * N + 1);
    if (N <= 50) {
        for (int u = 1; u <= 2 * N; ++u) {
            for (int v = u + 1; v <= 2 * N; ++v) {
                const auto kinds = Query({ u, v });
                if (kinds == 1) {
                    graph[u].push_back(v);
                    graph[v].push_back(u);
                }
            }
        }
    }
    else {
        for (int u = 1; u <= N; ++u) {
            const auto dif = [&](Vec<int> vec) {
                vec.push_back(u);
                return (int) vec.size() - Query(vec);
            };
            std::queue<std::pair<Vec<int>, int>> que;
            {
                Vec<int> cand(N);
                std::iota(cand.begin(), cand.end(), N + 1);
                que.emplace(cand, dif(cand));
            }
            while (!que.empty()) {
                const auto [vec, d] = que.front();
                que.pop();
                if (vec.size() == 1) {
                    const auto v = vec.front();
                    graph[u].push_back(v);
                    graph[v].push_back(u);
                    continue;
                }
                Vec<int> left(vec.begin(), vec.begin() + vec.size() / 2);
                Vec<int> right(vec.begin() + vec.size() / 2, vec.end());
                if (d == 1) {
                    const auto l = dif(left);
                    if (l == 0) {
                        que.emplace(right, 1);
                    }
                    else {
                        que.emplace(left, 1);
                        que.emplace(right, dif(right));
                    }
                }
                else {
                    const auto l = dif(left);
                    if (l == 0) {
                        que.emplace(right, 2);
                    }
                    else {
                        que.emplace(left, l);
                        const auto r = dif(right);
                        if (r != 0) {
                            que.emplace(right, r);
                        }
                    }
                }
            }
        }
    }
    Vec<Vec<int>> prob(2 * N + 1, Vec<int>(2 * N + 1));
    for (int u = 1; u <= 2 * N; ++u) {
        const auto size = (int) graph[u].size();
        if (size == 1) {
            prob[u][graph[u].front()] = true;
        }
        else {
            for (int i = 0; i < size; ++i) {
                for (int j = 0; j < i; ++j) {
                    const auto x = graph[u][i];
                    const auto y = graph[u][j];
                    if (Query({ u, x, y }) == 1) {
                        prob[u][x] = 1;
                        prob[u][y] = 1;
                    }
                }
            }
        }
    }
    for (int u = 1; u <= 2 * N; ++u) {
        for (int v = u + 1; v <= 2 * N; ++v) {
            if (prob[u][v] == 1 && prob[v][u] == 1) {
                Answer(u, v);
            }
        }
    }
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 32 ms 364 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 364 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 2 ms 364 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 33 ms 492 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 32 ms 364 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -