oj.uz

Submission #918938

# Submission time Handle Problem Language Result Execution time Memory
918938 2024-01-30T21:34:17 Z vjudge1 Chameleon's Love (JOI20_chameleon) C++17
44 / 100
 32 ms 608 KB 
#include "chameleon.h"

#include <bits/stdc++.h>
using namespace std;
namespace std {

template <class Fun>
class y_combinator_result {
        Fun fun_;

       public:
        template <class T>
        explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

        template <class... Args>
        decltype(auto) operator()(Args &&...args) {
                return fun_(std::ref(*this), std::forward<Args>(args)...);
        }
};

template <class Fun>
decltype(auto) y_combinator(Fun &&fun) {
        return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

/* Example
        auto fun = y_combinator([&](auto self, int x) -> void {
                self(x + 1);
        });
*/

}  // namespace std
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void Solve(int N) {
        auto ask = [&](vector<int> p) {
                for (auto &x : p) x++;
                return Query(p);
        };

        vector<vector<int>> one_match(N * 2);

        for (int i = 0; i < N * 2; i++) {
                vector<int> vis(i, -1);
                auto dfs = y_combinator([&](auto dfs, int u, int _) -> void {
                        vis[u] = _;
                        for (int v : one_match[u]) {
                                if (vis[v] == -1) dfs(v, _ ^ 1);
                        }
                });
                for (int j = 0; j < i; j++) {
                        if (vis[j] == -1) dfs(j, 0);
                }
                for (int z = 0; z < 2; z++) {
                        vector<int> a;
                        for (int j = 0; j < i; j++) {
                                if (vis[j] == z) a.emplace_back(j);
                        }
                        while (true) {
                                vector<int> rem(a.size());
                                iota(rem.begin(), rem.end(), 1);
                                for (int j = 1; j <= a.size(); j <<= 1) {
                                        vector<int> what(1, i);
                                        for (int k : rem) {
                                                if (k & j) what.emplace_back(a[k - 1]);
                                        }
                                        int ok = what.size() == 1 ? 0 : (ask(what) != what.size());
                                        vector<int> tmp;
                                        for (int k : rem) {
                                                if (((k & j) > 0) == ok) tmp.emplace_back(k);
                                        }
                                        swap(rem, tmp);
                                }
                                if (rem.size() == 0) break;
                                assert(rem.size() == 1);
                                int x = rem[0];
                                x--;
                                one_match[i].emplace_back(a[x]);
                                one_match[a[x]].emplace_back(i);
                                a.erase(a.begin() + x);
                        }
                }
        }

        vector<int> answer(2 * N);
        vector<int> love(2 * N);
        vector<int> evol(2 * N);
        vector<int> done(N * 2, 0);
        for (int i = 0; i < 2 * N; i++) {
                if (one_match[i].size() == 1) {
                        if (answer[i]) continue;
                        answer[i] = 1;
                        answer[one_match[i][0]] = 1;
                        Answer(i + 1, one_match[i][0] + 1);
                } else {
                        int last = -1;
                        while (done[i] == 0) {
                                done[i] = 1;
                                int a = one_match[i][0];
                                int b = one_match[i][1];
                                int c = one_match[i][2];
                                if (last == -1) {
                                        if (ask({i, a, b}) == 1) {
                                                love[i] = c;
                                                evol[c] = i;
                                        } else if (ask({i, a, c}) == 1) {
                                                love[i] = b;
                                                evol[b] = i;
                                        } else {
                                                love[i] = a;
                                                evol[a] = i;
                                        }
                                } else {
                                        if (last != a && ask({i, last, a}) == 1) {
                                                int nxt = last ^ b ^ c;
                                                love[i] = nxt;
                                                evol[nxt] = i;
                                                last = i;
                                                i = nxt;
                                        } else if (last != b && ask({i, last, b}) == 1) {
                                                int nxt = last ^ a ^ c;
                                                love[i] = nxt;
                                                evol[nxt] = i;
                                                last = i;
                                                i = nxt;
                                        } else {
                                                int nxt = last ^ a ^ b;
                                                love[i] = nxt;
                                                evol[nxt] = i;
                                                last = i;
                                                i = nxt;
                                        }
                                }
                        }
                }
        }
        for (int i = 0; i < 2 * N; i++) {
                if (answer[i]) continue;
                for (int j : one_match[i]) {
                        if (j == love[i]) continue;
                        if (j == evol[i]) continue;
                        answer[i] = answer[j] = 1;
                        Answer(i + 1, j + 1);
                }
        }
}

Compilation message

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:62:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                                 for (int j = 1; j <= a.size(); j <<= 1) {
      |                                                 ~~^~~~~~~~~~~
chameleon.cpp:67:84: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |                                         int ok = what.size() == 1 ? 0 : (ask(what) != what.size());
      |                                                                          ~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 31 ms 344 KB Output is correct
4 Correct 31 ms 608 KB Output is correct
5 Correct 32 ms 344 KB Output is correct
6 Correct 31 ms 548 KB Output is correct
7 Correct 31 ms 344 KB Output is correct
8 Correct 32 ms 344 KB Output is correct
9 Correct 31 ms 536 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 31 ms 344 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 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 31 ms 344 KB Output is correct
4 Correct 31 ms 608 KB Output is correct
5 Correct 32 ms 344 KB Output is correct
6 Correct 31 ms 548 KB Output is correct
7 Correct 31 ms 344 KB Output is correct
8 Correct 32 ms 344 KB Output is correct
9 Correct 31 ms 536 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 540 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Incorrect 31 ms 344 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -