Submission #935512

#	Time	Username	Problem	Language	Result	Execution time	Memory
935512		1075508020060209tc	Chameleon's Love (JOI20_chameleon)	C++14	100 / 100	33 ms	648 KiB

chameleon

#include "chameleon.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>e[2010];

int slv(int a,vector<int>vc){
if(Query({a,vc[0],vc[1]})==1){
    return vc[2];
}
if(Query({a,vc[0],vc[2]})==1){
    return vc[1];
}
return vc[0];
}

void fsolve(){
vector<int>lvlv(n*2+10,0);
vector<int>ans(n*2+10,0);
vector<int>love(n*2+10,0);

for(int i=1;i<=n*2;i++){
    if(e[i].size()==1){
        ans[i]=e[i][0];
        lvlv[i]=1;
    }
}
for(int i=1;i<=n*2;i++){
    if(e[i].size()==3){
        love[i]=slv(i,e[i]);
    }
}
for(int i=1;i<=n*2;i++){
    if(e[i].size()==1){continue;}
    if(e[i].size()==3){
    if(e[i][0]!=love[i]&&(love[e[i][0]]!=i||lvlv[e[i][0]])){ans[i]=e[i][0];}
    if(e[i][1]!=love[i]&&(love[e[i][1]]!=i||lvlv[e[i][1]])){ans[i]=e[i][1];}
    if(e[i][2]!=love[i]&&(love[e[i][2]]!=i||lvlv[e[i][2]])){ans[i]=e[i][2];}
    }
}
for(int i=1;i<=n*2;i++){
    if(ans[i]){
        ans[ans[i]]=i;
    }
}

for(int i=1;i<=n*2;i++){
    if(ans[i]<i&&ans[i]){
        Answer(i,ans[i]);
    }
}
}

int ask(int l,int r,vector<int>&ar,int v){
if(r>=ar.size()){return 1;}
vector<int>vc;
for(int i=l;i<=r;i++){
    vc.push_back(ar[i]);
}
vc.push_back(v);
if(Query(vc)<vc.size()){return 1;}
return 0;
}

vector<int>adde(int nw,vector<int>ar){
vector<int>ret;
vector<int>vc=ar;
vc.push_back(nw);
if(Query(vc)==vc.size()){return ret;}
int l;int r;
l=0;r=ar.size();
int lc=0;
for(int tc=0;tc<=2;tc++){
r=ar.size();
while(l<r){
    int mi=l+(r-l)/2;
    if(ask(lc,mi,ar,nw)){
        r=mi;
    }else{
        l=mi+1;
    }
}
if(l<ar.size()){
    ret.push_back(ar[l]);
}
l+=1;
lc=l;
}
return ret;
}


int uf[2010];
int uv[2010];
int usz[2010];
int fin(int x){
if(uf[x]==x){return x;}
return fin(uf[x]);
}
int finv(int x){
if(uf[x]==x){return 0;}
return (finv(uf[x])+uv[x])%2;
}
void mrg(int a,int b){
int pa=fin(a);int pb=fin(b);
int va=finv(a);int vb=finv(b);
if(pa==pb){return;}
if(usz[pa]<usz[pb]){
    swap(pa,pb);
    swap(va,vb);
}
uf[pb]=pa;
usz[pa]+=usz[pb];
uv[pb]=(1^va^vb);
}

int vis[2010];
void Solve(int N){
n=N;
vector<int>duili;
duili.push_back(1);
vis[1]=1;
for(int i=2;i<=n+n;i++){
    vector<int>vc=duili;
    vc.push_back(i);
    if(Query(vc)==vc.size()){
        duili.push_back(i);
        vis[i]=1;
    }
}

for(int i=1;i<=n+n;i++){
    uf[i]=i;
    usz[i]=1;
    uv[i]=0;
}

for(int i=1;i<=n+n;i++){
    if(vis[i]){continue;}
    vector<int>vcl;vector<int>vcr;
    for(int j=1;j<=n+n;j++){
        if(vis[j]==0){continue;}
        if(finv(j)==0){
            vcl.push_back(j);
        }else{
            vcr.push_back(j);
        }
    }
    vector<int>tvc=adde(i,vcl);
    vector<int>tvc2=adde(i,vcr);
    for(int v:tvc){
        mrg(i,v);
        e[i].push_back(v);
        e[v].push_back(i);
    }
    for(int v:tvc2){
        mrg(i,v);
        e[i].push_back(v);
        e[v].push_back(i);
    }
    vis[i]=1;
}


fsolve();
}
/*
4
1 0 1 0 0 1 1 0
4 4 1 2 1 2 3 3
4 3 8 7 6 5 2 1


*/

Compilation message (stderr)

chameleon.cpp: In function 'int ask(int, int, std::vector<int>&, int)':
chameleon.cpp:56:5: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 | if(r>=ar.size()){return 1;}
      |    ~^~~~~~~~~~~
chameleon.cpp:62:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 | if(Query(vc)<vc.size()){return 1;}
      |    ~~~~~~~~~^~~~~~~~~~
chameleon.cpp: In function 'std::vector<int> adde(int, std::vector<int>)':
chameleon.cpp:70:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 | if(Query(vc)==vc.size()){return ret;}
      |    ~~~~~~~~~^~~~~~~~~~~
chameleon.cpp:84:5: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 | if(l<ar.size()){
      |    ~^~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:127:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     if(Query(vc)==vc.size()){
      |        ~~~~~~~~~^~~~~~~~~~~

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