Submission #945070

#	Time	Username	Problem	Language	Result	Execution time	Memory
945070		Tuanlinh123	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	24 ms	564 KiB

chameleon

#include "chameleon.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

void Solve(ll n) 
{
    vector <vector <ll>> sus(n*2+1);
    vector <ll> love(n*2+1, 0), loved(n*2+1, 0), res(n*2+1, 0), col(n*2+1, 0);
    auto change=[&](ll s)
    {
        queue <ll> q;
        vector <bool> check(n*2+1, 0);
        check[s]=1, col[s]^=1, q.push(s);
        while (!q.empty())
        {
            ll u=q.front(); q.pop();
            for (ll v:sus[u])
                if (!check[v])
                    check[v]=1, col[v]^=1, q.push(v);
        }
    };
    auto addedge=[&](ll u, ll v)
    {
        if (col[u]==col[v]) change(u);
        sus[u].pb(v), sus[v].pb(u);
    };
    auto ask=[&](vector <ll> q, ll o) 
    {
        q.pb(o); 
        return (Query(q)!=sz(q));
    };
    for (ll i=1; i<=n*2; i++)
    {
        vector <ll> num[2];
        for (ll j=1; j<i; j++) num[col[j]].pb(j);
        for (ll j=0; j<2; j++)
        {
            if (!sz(num[j])) continue;
            ll p=0, en=sz(num[j]);
            while (p<en)
            {
                if (!ask(vector <ll>(num[j].begin()+p, num[j].end()), i)) break;
                ll lo=p, hi=en-1;
                while (hi>lo)
                {
                    ll mid=(lo+hi+1)/2;
                    if (!ask(vector <ll>(num[j].begin()+lo, num[j].begin()+mid), i))
                        lo=mid;
                    else hi=mid-1;
                }
                addedge(i, num[j][lo]), p=lo+1;
            }
        }
    }
    for (ll i=1; i<=n*2; i++)
    {
        if (sz(sus[i])==1)
        {
            res[i]=sus[i][0], res[sus[i][0]]=i;
            continue;
        }
        assert(sz(sus[i])==3);
        for (ll j=0; j<3; j++)
            if (Query(vector <ll>{i, sus[i][j], sus[i][(j+1)%3]})==1)
                love[i]=sus[i][(j+2)%3], loved[sus[i][(j+2)%3]]=i;
    }
    for (ll i=1; i<=n*2; i++)
    {
        if (sz(sus[i])==1) continue;
        for (ll j:sus[i])
            if (j!=love[i] && j!=loved[i])
                res[i]=j, res[j]=i;
    }
    for (ll i=1; i<=n*2; i++)
    {
        if (!res[i]) continue;
        Answer(i, res[i]), res[i]=res[res[i]]=0;
    }
}

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