Submission #582712

#	Time	Username	Problem	Language	Result	Execution time	Memory
582712		elkernos	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	65 ms	540 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>

using namespace std;

void Solve(int n)
{
    n = 2 * n;
    vector<int> nxt(n + 1);
    vector<vector<int>> g(n + 1);
    int used = 0;
    for(int i = 1; i <= n; i++) {
        int dorzuc = -1;
        vector<int> col(i, -1);
        function<void(int, bool)> dfs = [&](int u, bool newcol) {
            col[u] = newcol;
            for(int to : g[u]) {
                if(col[to] == -1) {
                    dfs(to, !newcol);
                }
            }
        };
        vector<vector<int>> zbio(2);
        for(int j = 1; j < i; j++) {
            if(col[j] == -1) {
                dfs(j, 0);
            }
            zbio[col[j]].push_back(j);
        }
        for(int j = 0; j < 2; j++) {
            int gdz = 0;
            auto pyt = [&](int ii, int a, int b, int add) {
                vector<int> q;
                for(int i = a; i <= b; i++) {
                    q.push_back(zbio[ii][i]);
                }
                q.push_back(add);
                return Query(q) != (int)q.size();
            };
            while(gdz < (int)zbio[j].size() && pyt(j, gdz, (int)zbio[j].size() - 1, i)) {
                int lo = gdz, hi = (int)zbio[j].size() - 1, ans = -1;
                while(lo <= hi) {
                    int m = (lo + hi) / 2;
                    if(pyt(j, gdz, m, i)) {
                        ans = m;
                        hi = m - 1;
                    }
                    else {
                        lo = m + 1;
                    }
                }
                assert(ans != -1);
                g[i].push_back(zbio[j][ans]);
                g[zbio[j][ans]].push_back(i);
                gdz = ans + 1;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if((int)g[i].size() == 1) {
            continue;
        }
        vector<vector<int>> pytaj = {{i, g[i][0], g[i][1]},
                                     {i, g[i][0], g[i][2]},
                                     {i, g[i][1], g[i][2]}};
        random_shuffle(pytaj.begin(), pytaj.end());
        vector<int> all = {i, g[i][0], g[i][1], g[i][2]};
        for(vector<int> pyt : pytaj) {
            if(Query(pyt) == 1) {
                for(int ii : all) {
                    if(find(pyt.begin(), pyt.end(), ii) == pyt.end()) {
                        nxt[i] = ii;
                    }
                }
                break;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        int ans = -1;
        for(int x : g[i]) {
            if(x != nxt[i] && nxt[x] != i) {
                ans = x;
            }
        }
        assert(ans != -1);
        if(ans > i) {
            Answer(i, ans);
        }
    }
}

Compilation message (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:13:13: warning: unused variable 'dorzuc' [-Wunused-variable]
   13 |         int dorzuc = -1;
      |             ^~~~~~
chameleon.cpp:11:9: warning: unused variable 'used' [-Wunused-variable]
   11 |     int used = 0;
      |         ^~~~

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36