Submission #954387

#	Time	Username	Problem	Language	Result	Execution time	Memory
954387		andrei_boaca	Chameleon's Love (JOI20_chameleon)	C++17	100 / 100	41 ms	1116 KiB

chameleon

#include "chameleon.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
namespace
{
    vector<int> muchii[1005];
    int n;
    int cul[1005];
    int p[1005],par[1005];
    bool use[1005];
    int nr[1005];
    void dfs(int nod)
    {
        for(int i:muchii[nod])
            if(cul[i]==-1)
            {
                cul[i]=1-cul[nod];
                dfs(i);
            }
    }
    void plsfind(vector<int> v,int me)
    {
        if(v.empty()||muchii[me].size()==3)
            return;
        int st=0;
        int dr=v.size();
        vector<int> preventiv=v;
        preventiv.push_back(me);
        int x=Query(preventiv);
        if(x==preventiv.size())
            return;
        dr-=2;
        int poz=dr+1;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            vector<int> nodes;
            nodes.push_back(me);
            for(int i=0;i<=mij;i++)
                nodes.push_back(v[i]);
            int val=Query(nodes);
            if(val<nodes.size())
            {
                poz=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        if(poz>=v.size())
            return;
        muchii[me].push_back(v[poz]);
        muchii[v[poz]].push_back(me);
        vector<int> aux;
        for(int i=poz+1;i<v.size();i++)
            aux.push_back(v[i]);
        plsfind(aux,me);
    }
}
void Solve(int N)
{
    n=N;
    for(int i=2;i<=2*n;i++)
    {
        for(int j=1;j<=2*n;j++)
            cul[j]=-1;
        for(int j=1;j<i;j++)
            if(cul[j]==-1)
            {
                cul[j]=0;
                dfs(j);
            }
        vector<int> a,b;
        for(int j=1;j<i;j++)
        {
            if(cul[j]==0)
                a.push_back(j);
            else
                b.push_back(j);
        }
        plsfind(a,i);
        plsfind(b,i);
    }
    for(int i=1;i<=2*n;i++)
    {
        int lg=muchii[i].size();
        if(muchii[i].size()==3)
        {
            for(int j=0;j<muchii[i].size();j++)
                nr[j]=0;
            for(int j=0;j<muchii[i].size();j++)
                for(int k=j+1;k<muchii[i].size();k++)
                {
                    int val=Query({i,muchii[i][j],muchii[i][k]});
                    if(val==2)
                    {
                        nr[j]++;
                        nr[k]++;
                    }
                }
            for(int j=0;j<muchii[i].size();j++)
                if(nr[j]==2)
                    p[i]=muchii[i][j];
        }
    }
    for(int i=1;i<=2*n;i++)
    {
        if(p[i]==0)
        {
            if(use[i])
                continue;
            Answer(i,muchii[i][0]);
            use[i]=1;
            use[muchii[i][0]]=1;
            continue;
        }
        vector<int> nodes;
        int nod=i;
        while(true)
        {
            if(nod==i&&nodes.size()>0)
                break;
            nodes.push_back(nod);
            int fiu=p[nod];
            par[fiu]=nod;
            nod=fiu;
        }
        for(int j:nodes)
            if(!use[j])
            {
                int a=muchii[j][0]^muchii[j][1]^muchii[j][2]^par[j]^p[j];
                use[a]=1;
                use[j]=1;
                Answer(a,j);
            }
    }
}

Compilation message (stderr)

chameleon.cpp: In function 'void {anonymous}::plsfind(std::vector<int>, int)':
chameleon.cpp:31:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         if(x==preventiv.size())
      |            ~^~~~~~~~~~~~~~~~~~
chameleon.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             if(val<nodes.size())
      |                ~~~^~~~~~~~~~~~~
chameleon.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         if(poz>=v.size())
      |            ~~~^~~~~~~~~~
chameleon.cpp:56:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int i=poz+1;i<v.size();i++)
      |                         ~^~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:90:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             for(int j=0;j<muchii[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~~
chameleon.cpp:92:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             for(int j=0;j<muchii[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~~
chameleon.cpp:93:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                 for(int k=j+1;k<muchii[i].size();k++)
      |                               ~^~~~~~~~~~~~~~~~~
chameleon.cpp:102:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |             for(int j=0;j<muchii[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~~
chameleon.cpp:87:13: warning: unused variable 'lg' [-Wunused-variable]
   87 |         int lg=muchii[i].size();
      |             ^~

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