Submission #1272041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272041		tvgk	Chameleon's Love (JOI20_chameleon)	C++20	100 / 100	39 ms	508 KiB

chameleon

#include "chameleon.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define fi first
#define se second
#define ii pair<ll, ll>
const int mxN = 1e3 + 7;

bool vis[mxN];
vector<int> vc[2], w[mxN];

void DFS(int j, bool tt)
{
    if (vis[j])
        return;
    vis[j] = 1;
    vc[tt].push_back(j);

    for (int i : w[j])
        DFS(i, tt ^ 1);
}

void Cut(int sz)
{
    vc[0].clear();
    vc[1].clear();
    for (int i = 1; i <= sz; i++)
        vis[i] = 0;

    for (int i = 1; i <= sz; i++)
        DFS(i, 0);
}

bool Binary(bool tt, int nw)
{
    vc[tt].push_back(nw);
    if (Query(vc[tt]) == vc[tt].size())
        return 0;
    vc[tt].pop_back();

    int l = 0, r = vc[tt].size() - 1;
    while (l < r)
    {
        int mid = (l + r) / 2;

        vector<int> ask;
        ask.push_back(nw);
        for (int i = l; i <= mid; i++)
            ask.push_back(vc[tt][i]);

        if (Query(ask) == ask.size())
            l = mid + 1;
        else
            r = mid;
    }

    l = vc[tt][l];
    w[l].push_back(nw);
    w[nw].push_back(l);

    vector<int> tmp;
    for (int i : vc[tt])
    {
        if (i == l)
            continue;
        tmp.push_back(i);
    }
    vc[tt] = tmp;

    return 1;
}

void Solve(int n)
{
    n *= 2;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= 1; j++)
            while (Binary(j, i)) {}
        Cut(i);
    }

    for (int i = 1; i <= n; i++)
        vis[i] = 0;

    for (int i = 1; i <= n; i++)
    {
//        cout << i << " : ";
//        for (int j : w[i])
//            cout << j << " ";
//        cout << '\n';

        if (w[i].size() == 3)
        {
            int ans[3];
            for (int j = 0; j < 3; j++)
            {
                vector<int> vc;
                vc.push_back(w[i][j]);
                vc.push_back(w[i][(j + 1) % 3]);
                vc.push_back(i);
                ans[j] = Query(vc);

                if (ans[j] == 1)
                {
                    w[i] = vc;
                    w[i].pop_back();
                    break;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (vis[i])
            continue;

        for (int j : w[i])
        {
            for (int u : w[j])
            {
                if (u == i)
                {
                    Answer(u, j);
                    vis[j] = 1;
                }
            }
        }
    }
}

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