Submission #1289291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289291		efex12	Chameleon's Love (JOI20_chameleon)	C++20	100 / 100	46 ms	540 KiB

chameleon

#include "chameleon.h"
#include<bits/stdc++.h>
#define pint pair<int,int>
#define N 200005
#define pb push_back
#define ff first
#define ss second
#define mod 1000000007
#define INF 1000000000000000005
#define pu push
 
using namespace std;

vector<pint> v[N];
int group[N];

void dfs(int ind,int depth)
{
    if(group[ind]!=-1)
        return;
    group[ind]=depth;
    for(int i=0;i<v[ind].size();i++)
    {
        dfs(v[ind][i].ff,(1-depth));
    }
    return;
}

void Solve(int n)
{
    for(int i=1;i<2*n;i++)
    {
        for(int j=0;j<i;j++)
        {
            group[j]=-1;
        }
        for(int j=0;j<i;j++)
        {
            dfs(j,0);
        }
        vector<int> x[3];
        for(int j=0;j<i;j++)
        {
            x[group[j]].pb(j);
        }
        for(int z=0;z<2;z++)
        {
            while(1)
            {
                vector<int> temp;
                if(!x[z].empty())
                {
                    for(auto aa:x[z])
                        temp.pb(aa+1);
                }
                temp.pb(i+1);
                if(temp.empty()||Query(temp)==temp.size())
                    break;
                int r=x[z].size(),l=0,ans=0;
                while(l<=r)
                {
                    temp.clear();
                    int mid=(l+r)/2;
                    for(int j=0;j<mid;j++)
                    {
                        temp.pb(x[z][j]+1);
                    }
                    temp.pb(i+1);
                    if(temp.empty()||Query(temp)==temp.size())
                    {
                        ans=mid;
                        l=mid+1;
                    }
                    else
                    {
                        r=mid-1;
                    }
                }
                v[i].pb({x[z][ans],-1});
                v[x[z][ans]].pb({i,-1});
                vector<int> now;
                for(int i=0;i<x[z].size();i++)
                {
                    if(i!=ans)
                        now.pb(x[z][i]);
                }
                x[z]=now;
            }
        }
    }
    /*
4
1 0 1 0 0 1 1 0
4 4 1 2 1 2 3 3
4 3 8 7 6 5 2 1
    */
    for(int i=0;i<2*n;i++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            if(v[i][j].ss==-1)
                v[i][j].ss=3;
        }
    }
    for(int i=0;i<2*n;i++)
    {
        if(v[i].size()==1)
        {
            v[i][0].ss=3;
            for(int j=0;j<v[v[i][0].ff].size();j++)
                if(v[v[i][0].ff][j].ff==i)
                    v[v[i][0].ff][j].ss=3;
        }
        else
        {
            vector<int> temp;
            temp.pb(i+1);
            temp.pb(v[i][0].ff+1);
            temp.pb(v[i][1].ff+1);
            if(Query(temp)==1)
            {
                v[i][2].ss=1;
                for(int j=0;j<v[v[i][2].ff].size();j++)
                {
                    if(v[v[i][2].ff][j].ff==i)
                        v[v[i][2].ff][j].ss=2;
                }
                continue;
            }
            temp.pop_back();
            temp.pb(v[i][2].ff+1);
            if(Query(temp)==1)
            {
                v[i][1].ss=1;
                for(int j=0;j<v[v[i][1].ff].size();j++)
                {
                    if(v[v[i][1].ff][j].ff==i)
                        v[v[i][1].ff][j].ss=2;
                }
                continue;
            }
            v[i][0].ss=1;
            for(int j=0;j<v[v[i][0].ff].size();j++)
            {
                if(v[v[i][0].ff][j].ff==i)
                    v[v[i][0].ff][j].ss=2;
            }
        }
    }
    int ok[2*n];
    for(int i=0;i<2*n;i++)
        ok[i]=0;
    for(int i=0;i<2*n;i++)
    {
        if(ok[i]==0)
        {
            for(int j=0;j<v[i].size();j++)
            {
                if(v[i][j].ss==3)
                {
                    Answer(i+1,v[i][j].ff+1);
                    ok[i]=1;
                    ok[v[i][j].ff]=1;
                    break;
                }
            }
        }
    }
}

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