제출 #278018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
278018		MKopchev	카멜레온의 사랑 (JOI20_chameleon)	C++14	24 / 100	48 ms	512 KiB

chameleon

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

using namespace std;

const int nmax=1e3+42;

vector< pair<int,int> > edges;

vector<int> adj[nmax];

int n_;

int colour[nmax];

void dfs(int node,int col)
{
    if(colour[node]!=-1)return;
    colour[node]=col;

    for(auto k:adj[node])
        dfs(k,!col);
}

void add_edge(int u,int v)
{
    //cout<<"edge "<<u<<" "<<v<<endl;

    adj[u].push_back(v);
    adj[v].push_back(u);
}
void go(int original,vector<int> other)
{
    if(other.size()==0)return;

    vector<int> help=other;
    help.push_back(original);

    if(Query(help)==help.size())return;

    if(other.size()==1)
    {
        add_edge(original,other[0]);
        return;
    }

    vector<int> le={},ri={};

    for(int i=0;i<other.size();i++)
        if(i%2==0)le.push_back(other[i]);
        else ri.push_back(other[i]);

    go(original,le);
    go(original,ri);
}
void make()
{
    for(int i=1;i<=2*n_;i++)
    {
        memset(colour,-1,sizeof(colour));

        for(int j=1;j<i;j++)
            if(colour[j]==-1)dfs(j,0);

        vector<int> groups[2]={{},{}};

        for(int j=1;j<i;j++)
            groups[colour[j]].push_back(j);

        go(i,groups[0]);
        go(i,groups[1]);
    }
}

int love[nmax];

bool solved[nmax];

set<int> blocked[nmax];

void Solve(int N)
{
    n_=N;

    make();

    for(int i=1;i<=2*n_;i++)
        if(solved[i]==0)
        {
            if(adj[i].size()==1)
            {
                Answer(i,adj[i][0]);
                solved[i]=1;
                solved[adj[i][0]]=1;
            }
            else
            {
                if(Query({i,adj[i][0],adj[i][1]})==1)love[i]=adj[i][2];
                else if(Query({i,adj[i][0],adj[i][2]})==1)love[i]=adj[i][1];
                else love[i]=adj[i][0];

                blocked[i].insert(love[i]);
                blocked[love[i]].insert(i);
            }
        }

    for(int i=1;i<=2*n_;i++)
        if(solved[i]==0)
        {
            for(auto k:adj[i])
                if(blocked[i].count(k)==0)
                {
                    solved[i]=1;
                    solved[k]=1;

                    Answer(i,k);

                    break;
                }
        }
}

컴파일 시 표준 에러 (stderr) 메시지

chameleon.cpp: In function 'void go(int, std::vector<int>)':
chameleon.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     if(Query(help)==help.size())return;
      |        ~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0;i<other.size();i++)
      |                 ~^~~~~~~~~~~~~

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