Submission #734899

#	Time	Username	Problem	Language	Result	Execution time	Memory
734899		mosiashvililuka	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	39 ms	456 KiB

chameleon

#include<bits/stdc++.h>
#include "chameleon.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,bo[1009],lef,rig,mid,in[1009],out[1009],col[1009],FX[1009],cnt;
vector <int> v,vv,D[1009],F,S;
int determine(vector <int> q){
    vector <int> v;
    int A[5];
    v.clear();
    v.push_back(q[0]);v.push_back(q[1]);v.push_back(q[2]);
    A[1]=Query(v);
    v.clear();
    v.push_back(q[0]);v.push_back(q[1]);v.push_back(q[3]);
    A[2]=Query(v);
    v.clear();
    v.push_back(q[0]);v.push_back(q[2]);v.push_back(q[3]);
    A[3]=Query(v);
    if(A[1]==A[2]) return q[1];
    if(A[1]==A[3]) return q[2];
    if(A[2]==A[3]) return q[3];
}
void dfs(int q){
    FX[q]=cnt;
    col[q]=3-col[q];
    for(vector <int>::iterator it=D[q].begin(); it!=D[q].end(); it++){
        if(FX[(*it)]==cnt) continue;
        dfs((*it));
    }
}
void mrg(int q, int w){
    if(col[q]!=col[w]) return;
    cnt++;
    dfs(w);
}
void DO(vector <int> v){
    if(v.size()==0) return;
    int j,ind=v.size();
    for(int TA=1; TA<=3; TA++){
        lef=-1;rig=ind;
        if(rig<=0) break;
        vv.clear();
        for(j=0; j<ind; j++){
            vv.push_back(v[j]);
        }
        vv.push_back(i);
        c=Query(vv);
        if(c==vv.size()) break;
        lef=0;
        while(1){
            if(lef+1>=rig) break;
            mid=(lef+rig)/2;
            vv.clear();
            for(j=mid; j<ind; j++){
                vv.push_back(v[j]);
            }
            vv.push_back(i);
            c=Query(vv);
            if(c==vv.size()){
                rig=mid;
            }else{
                lef=mid;
            }
        }
        mrg(v[lef],i);
        D[v[lef]].push_back(i);
        D[i].push_back(v[lef]);
        ind=lef;
    }
}
void Solve(int NN) {
    a=NN;
    for(i=0; i<=2*a+1; i++){
        bo[i]=0;
    }
    for(i=1; i<=a*2; i++){
        D[i].push_back(i);col[i]=1;
    }
    for(i=2; i<=a*2; i++){
        F.clear();S.clear();
        for(j=1; j<i; j++){
            if(col[j]==1){
                F.push_back(j);
            }else{
                S.push_back(j);//col[j]==2
            }
        }
        DO(F);
        if(D[i].size()==4) continue;
        DO(S);
    }
    //
    //
    for(i=1; i<=a*2; i++){
        if(D[i].size()>2){
            c=determine(D[i]);//romelic shedis i-shi
            in[i]=c;
            out[c]=i;
        }
    }

    for(i=1; i<=a*2; i++){
        if(bo[i]!=0) continue;
        jj=0;
        for(ii=1; ii<D[i].size(); ii++){
            j=D[i][ii];
            if(bo[j]!=0) continue;
            if(i==j) continue;
            if(j==in[i]||j==out[i]) continue;
            jj=j;break;
        }
        Answer(i,jj);
        bo[i]=1;bo[jj]=1;
    }
}

Compilation message (stderr)

chameleon.cpp: In function 'void DO(std::vector<int>)':
chameleon.cpp:47:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if(c==vv.size()) break;
      |            ~^~~~~~~~~~~
chameleon.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             if(c==vv.size()){
      |                ~^~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:104:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(ii=1; ii<D[i].size(); ii++){
      |                   ~~^~~~~~~~~~~~
chameleon.cpp: In function 'int determine(std::vector<int>)':
chameleon.cpp:7:18: warning: control reaches end of non-void function [-Wreturn-type]
    7 |     vector <int> v;
      |                  ^

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