Submission #278040

#	Time	Username	Problem	Language	Result	Execution time	Memory
278040		MKopchev	Chameleon's Love (JOI20_chameleon)	C++14	4 / 100	68 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;

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

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

        //there is an edge
        vector<int> active=other;

        while(active.size()>1)
        {
            vector<int> groups[2]={{},{}};

            for(int i=0;i<active.size();i++)
                groups[i%2].push_back(active[i]);

            groups[0].push_back(original);

            if(Query(groups[0])==groups[0].size())active=groups[1];
            else
            {
                groups[0].pop_back();
                active=groups[0];
            }

        }

        add_edge(original,active[0]);

        vector<int> other_new={};
        for(auto k:other)
            if(k!=active[0])other_new.push_back(k);

        other=other_new;
    }
}
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]);

        //cout<<"--- "<<query_count<<endl;
    }
}

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);
                }
        }
}

Compilation message (stderr)

chameleon.cpp: In function 'void go(int, std::vector<int>)':
chameleon.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         if(Query(help)==help.size())return;
      |            ~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for(int i=0;i<active.size();i++)
      |                         ~^~~~~~~~~~~~~~
chameleon.cpp:55:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             if(Query(groups[0])==groups[0].size())active=groups[1];
      |                ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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