Submission #1158791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158791		ace5	카멜레온의 사랑 (JOI20_chameleon)	C++20	100 / 100	50 ms	696 KiB

chameleon

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

using namespace std;

vector<set<int>> g;
vector<int> c;
vector<int> vis;
int n;

void dfs(int v,int tc)
{
    vis[v] = 1;
    c[v] = tc;
    for(auto u:g[v])
    {
        if(!vis[u])
        {
            dfs(u,tc^1);
        }
    }
    return ;
}


void Solve(int N)
{
    n = N;
    g.resize(2*n);
    c.resize(2*n);
    vis.resize(2*n);

    for(int j = 1;j < 2*n;++j)
    {
        for(auto& c:vis)
            c = 0;
        for(int u = 0;u < j;++u)
        {
            if(!vis[u])
                dfs(u,0);
        }
        vector<int> v[2];
        for(int u = 0;u < j;++u)
        {
           // cout << c[u] << ' ';
            v[c[u]].push_back(u+1);
        }
        //cout << endl;
        for(int i = 0;i < 2;++i)
        {
            while(true)
            {
                vector<int> cc = v[i];
                cc.push_back(j+1);
                if(Query(cc) == cc.size())
                {
                    break;
                }
                else
                {
                    int l = 0,r = v[i].size()-1;
                    while(l < r)
                    {
                        int m = (l+r)/2;
                        vector<int> ck;
                        for(int y = 0;y <= m;++y)
                        {
                            ck.push_back(v[i][y]);
                        }
                        ck.push_back(j+1);
                        if(Query(ck) == ck.size())
                        {
                            l = m+1;
                        }
                        else
                            r = m;
                    }
                    int v2 = v[i][l]-1;
                    //cout << j << ' ' << v2 << endl;
                    g[j].insert(v2);
                    g[v2].insert(j);
                    v[i].erase(v[i].begin() + l);
                }
            }
        }
    }
    vector<pair<int,int>> er;
    for(int i = 0;i < 2*n;++i)
    {
        if(g[i].size() == 3)
        {
            vector<int> v;
            for(auto u:g[i])
            {
                v.push_back(u);
            }
          //  cout << i << ' ' << v[0] << ' ' << v[1] << ' ' << v[2] << endl;
            int ans1 = Query({i+1,v[0]+1,v[1]+1});
            int ans2 = Query({i+1,v[0]+1,v[2]+1});
            pair<int,int> r;
            if(ans1 == 1)
                r = {i,v[2]};
            else if(ans2 == 1)
                r=  {i,v[1]};
            else
                r = {i,v[0]};
            er.push_back(r);
        }
    }
    for(auto [u,v] : er)
    {
        g[u].erase(v);
        g[v].erase(u);
    }
    for(int j = 0;j < 2*n;++j)
    {
        if(*g[j].begin() > j)
        {
            Answer(j+1,*g[j].begin()+1);
        }
    }
}

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