Submission #1272039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272039		tvgk	Chameleon's Love (JOI20_chameleon)	C++20	44 / 100	33 ms	488 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);
}

void Binary(int l, int r, bool tt, int nw)
{
    vector<int> ask;
    ask.push_back(nw);
    for (int i = l; i <= r; i++)
        ask.push_back(vc[tt][i]);
    int res = Query(ask);

    if (res == r - l + 2)
        return;

    if (l == r)
    {
        l = vc[tt][l];
        w[l].push_back(nw);
        w[nw].push_back(l);
        return;
    }

    int mid = (l + r) / 2;
    Binary(l, mid, tt, nw);
    Binary(mid + 1, r, tt, nw);
}

void Solve(int n)
{
    n *= 2;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= 1; j++)
            Binary(0, vc[j].size() - 1, j, i);
        Cut(i);
    }

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

    for (int i = 1; i <= n; i++)
    {
        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: 0 / 20
• Subtask 5: 0 / 36