Submission #1291976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291976		Ice_man	카멜레온의 사랑 (JOI20_chameleon)	C++20	100 / 100	45 ms	524 KiB

chameleon

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

#define maxn 1005
#define PB(x) push_back(x)


std::vector <int> v[maxn], bruh[maxn];
int c[maxn];


void dfs(int node)
{
    for(int nb : v[node])
    {
        if(c[nb] == -1)
        {
            if(c[node] == 0)
                c[nb] = 1;
            else
                c[nb] = 0;

            dfs(nb);
        }
    }
}



void Solve(int n)
{
    for(int node = 2; node <= 2 * n; node++)
    {
        for(int i = 1; i < node; i++)
            c[i] = -1;

        for(int i = 1; i < node; i++)
            if(c[i] == -1)
            {
                c[i] = 0;
                dfs(i);
            }


        std::vector <int> cc;
        for(int i = 1; i < node; i++)
            if(c[i] == 0)
                cc.PB(i);

        if(cc.size() > 0)
        {
            cc.PB(node);

            while(Query(cc) != cc.size())
            {
                int l = 0, r = cc.size() - 2;


                while(l < r)
                {
                    int mid = (l + r) / 2;

                    std::vector <int> pom;
                    for(int i = 0; i <= mid; i++)
                        pom.PB(cc[i]);
                    pom.PB(node);

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

                v[node].PB(cc[r]);
                v[cc[r]].PB(node);

                cc.erase(cc.begin() + r);
            }
        }

        cc.clear();

        for(int i = 1; i < node; i++)
            if(c[i] == 1)
                cc.PB(i);

        if(cc.size() > 0)
        {
            cc.PB(node);

            while(Query(cc) != cc.size())
            {
                int l = 0, r = cc.size() - 2;

                while(l < r)
                {
                    int mid = (l + r) / 2;

                    std::vector <int> pom;

                    for(int i = 0; i <= mid; i++)
                        pom.PB(cc[i]);
                    pom.PB(node);

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

                v[node].PB(cc[r]);
                v[cc[r]].PB(node);

                cc.erase(cc.begin() + r);
            }
        }
    }


    std::vector <int> gf(2 * n + 5);
    for(int node = 1; node <= 2 * n; node++)
    {
        if(v[node].size() == 1)
        {
            gf[node] = v[node][0];

            continue;
        }


        std::vector <int> pom = {node, v[node][0], v[node][1]};
        if(Query(pom) == 1)
        {
            bruh[node].PB(v[node][2]);
            bruh[v[node][2]].PB(node);

            continue;
        }

        pom = {node, v[node][0], v[node][2]};
        if(Query(pom) == 1)
        {
            bruh[node].PB(v[node][1]);
            bruh[v[node][1]].PB(node);

            continue;
        }

        pom = {node, v[node][1], v[node][2]};
        if(Query(pom) == 1)
        {
            bruh[node].PB(v[node][0]);
            bruh[v[node][0]].PB(node);

            continue;
        }
    }


    for(int node = 1; node <= 2 * n; node++)
    {
        if(gf[node] == 0)
        {
            std::map <int, int> opt;
            for(int nb : bruh[node])
                opt[nb] = 1;

            for(int nb : v[node])
                if(opt.find(nb) == opt.end())
                {
                    gf[node] = nb;
                    break;
                }
        }
    }


    for(int i = 1; i <= 2 * n; i++)
        if(i < gf[i])
            Answer(i , gf[i]);
}

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