Submission #954385

#TimeUsernameProblemLanguageResultExecution timeMemory
954385andrei_boacaChameleon's Love (JOI20_chameleon)C++17
44 / 100
46 ms1028 KiB
#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) { bool ok=0; if(me==4) ok=1; if(v.empty()) return; int st=0; int dr=v.size(); dr--; int poz=1e9; 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:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             if(val<nodes.size())
      |                ~~~^~~~~~~~~~~~~
chameleon.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         if(poz>=v.size())
      |            ~~~^~~~~~~~~~
chameleon.cpp:54:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int i=poz+1;i<v.size();i++)
      |                         ~^~~~~~~~~
chameleon.cpp:24:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   24 |         bool ok=0;
      |              ^~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |             for(int j=0;j<muchii[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~~
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:91:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                 for(int k=j+1;k<muchii[i].size();k++)
      |                               ~^~~~~~~~~~~~~~~~~
chameleon.cpp:100:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for(int j=0;j<muchii[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~~
chameleon.cpp:85:13: warning: unused variable 'lg' [-Wunused-variable]
   85 |         int lg=muchii[i].size();
      |             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...