#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<int>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
struct greateri
{
template<class T>
bool operator()(T const &a, T const &b) const { return a > b; }
};
int sex[5001];
map<int,int>gg;
int posi[5001][3];
ve posia[5001];
int vis[2001];
int yhebha[3001];
bool nal[2001];
bool ka1[5001];
int cores[5001];
int addi(int x,int l,int r,int cur)
{
if(posi[cur][0]>=l && posi[cur][0]<=r)x++;
if(posi[cur][1]>=l && posi[cur][1]<=r)x++;
return x;
}
int bestiole[5001];
void Solve(int N)
{
memset(posi,-1,sizeof posi);
memset(cores,-1,sizeof cores);
set<int>unknown;
N*=2;
for (int i = 1; i<N; ++i)
{
unknown.insert(i);
}
if(N/2<=50)
{sex[0]=0;
queue<int>yo;
yo.push(0);
while(!yo.empty())
{
auto u=yo.front();
yo.pop();
set<int>ko=unknown;
set<int>nexti;
for(auto it:ko)
{
ve hi;
hi.pb(u+1);hi.pb(it+1);
if(Query(hi)==1)
{
sex[it]=1-sex[u];
nexti.insert(it);
bestiole[u]++;
bestiole[it]++;
unknown.erase(it);
}
}
if(bestiole[u]!=1)
{
for(auto it:nexti)
{
yo.push(it);
}
}
if(yo.size()==0 && unknown.size()!=0){yo.push(*(unknown.begin()));unknown.erase(*(unknown.begin()));}
}}
else
{for (int i = N/2; i < N; ++i)
{
sex[i]=1;
}}
ve male,female;
for (int i = 0; i < N; ++i)
{
if(!sex[i])
{
male.pb(i);
}
else
{
female.pb(i);
}
}
memset(yhebha,-1,sizeof yhebha);
for (int i = 0; i < male.size(); ++i)
{
memset(nal,0,sizeof nal);
int low=0,high=female.size()-1;
int cur=male[i];
//debug(cur);
int posi1=-1,posi2=-1,posi3=-1;
while(low<=high)
{
int med=(low+high)/2;
ve yo;
yo.pb(cur+1);
for (int i=low; i <= med; ++i)
{
if(!nal[i])
yo.pb(female[i]+1);
}
int kol=Query(yo);
//debug(kol);
//debugs(med,low);
//kol=addi(kol,low,med,cur);
if(low==high)
{
if(kol==yo.size())
{
posi1=-1;
}
else
{
posi1=low;
}
break;
}
if(kol==yo.size())
{
low=med+1;
}
else
{
high=med;
}
}
low=0,high=female.size()-1;
//debugs(female[posi1],cur);
nal[posi1]=1;
posi[cur][0]=female[posi1];
posia[female[posi1]].pb(cur);
while(low<=high)
{
int med=(low+high)/2;
ve yo;
yo.pb(cur+1);
for (int i = low; i <= med; ++i)
{
if(!nal[i])
{yo.pb(female[i]+1);//debug(female[i]+1);
}
}
int kol=Query(yo);
//kol=addi(kol,low,med,cur);
if(low==high)
{
if(kol==yo.size())
{
posi2=-1;
}
else
{
posi2=low;
}
break;
}
if(kol==yo.size())
{
low=med+1;
}
else
{
high=med;
}
}
low=0,high=female.size()-1;
if(posi2!=-1)posi[cur][1]=female[posi2];
else posi[cur][1]=-1;
////debugs(female[posi2],cur);
nal[posi2]=1;
posia[female[posi1]].pb(cur);
while(low<=high)
{
int med=(low+high)/2;
ve yo;
yo.pb(cur+1);
for (int i = low; i <= med; ++i)
{
if(!nal[i])
{yo.pb(female[i]+1);//debug(female[i]+1);
}
}
int kol=Query(yo);
//kol=addi(kol,low,med,cur);
if(low==high)
{
if(kol==yo.size())
{
posi3=-1;
}
else
{
posi3=low;
}
break;
}
if(kol==yo.size())
{
low=med+1;
}
else
{
high=med;
}
}
if(posi3!=-1)posi[cur][2]=female[posi3];
else posi[cur][2]=-1;
if(posi2==-1 && posi3==-1)
{
ka1[cur]=1;
//debugs(posi1,female[posi1]);
//debugs(cur,female[posi1]);
Answer(cur+1,female[posi1]+1);
cores[female[posi1]]=cur;
}
posia[female[posi1]].pb(cur);
}
////debug(0);
bool ka=false;
for (int i = 0; i < male.size(); ++i)
{
int cur=male[i];
if(posi[cur][1]!=-1)
{
ve di;
di.pb(cur+1);
di.pb(posi[cur][0]+1);
di.pb(posi[cur][1]+1);
int yo = Query(di);
ve ka,fa;
ka.pb(cur+1);ka.pb(posi[cur][0]+1);ka.pb(posi[cur][2]+1);
fa.pb(cur+1);fa.pb(posi[cur][2]+1);fa.pb(posi[cur][1]+1);
int so = Query(ka);
int ko = Query(fa);
if(yo==1)
{
yhebha[posi[cur][2]]=cur;
//debugs(posi[cur][2],cur);
vis[cur]=1;
}
else if(so==1)
{
yhebha[posi[cur][1]]=cur;
//debugs(posi[cur][1],cur);
vis[cur]=2;
}
else
{
yhebha[posi[cur][0]]=cur;
vis[cur]=3;
//debugs(posi[cur][0],cur);
//debugs(cur,vis[cur]);
}
}
}
//vis[6]=3;
for (int i = 0; i < male.size(); ++i)
{
int cur=male[i];
int fem1=0,fem2=0;
if(!ka1[cur])
{
//debugs(cur,vis[cur]);
//int yo = Query([cur,posi[cur][0],posi[cur][1]]);
if(vis[cur]<=1)
{
fem1=posi[cur][0];
fem2=posi[cur][1];
}
else if(vis[cur]==2)
{
fem1=posi[cur][0];
fem2=posi[cur][2];
}
else
{
fem1=posi[cur][1];
fem2=posi[cur][2];
//debugs(posi[cur][1],posi[cur][2]);
}
{
if(yhebha[fem1]==-1 || yhebha[fem1]==cur)swap(fem1,fem2);
ve lom;
//debug(yhebha[fem1])
lom.pb(cur+1);
lom.pb(fem1+1);
lom.pb(yhebha[fem1]+1);
int sol=Query(lom);
//debugs(cores[fem1],cores[fem2]);
if(sol==1 || cores[fem2]!=-1)
{
//debugs(cur,fem1);
Answer(cur+1,fem1+1);
}
else
{
//debugs(cur,fem2);
Answer(cur+1,fem2+1);
}
}}
}
}
//code the AC sol !
// BS/queue/map
/*
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
chameleon.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("O3")
chameleon.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("unroll-loops")
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:101:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < male.size(); ++i)
~~^~~~~~~~~~~~~
chameleon.cpp:124:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(kol==yo.size())
~~~^~~~~~~~~~~
chameleon.cpp:134:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(kol==yo.size())
~~~^~~~~~~~~~~
chameleon.cpp:164:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(kol==yo.size())
~~~^~~~~~~~~~~
chameleon.cpp:174:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(kol==yo.size())
~~~^~~~~~~~~~~
chameleon.cpp:205:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(kol==yo.size())
~~~^~~~~~~~~~~
chameleon.cpp:215:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(kol==yo.size())
~~~^~~~~~~~~~~
chameleon.cpp:238:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < male.size(); ++i)
~~^~~~~~~~~~~~~
chameleon.cpp:253:17: warning: unused variable 'ko' [-Wunused-variable]
int ko = Query(fa);
^~
chameleon.cpp:276:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < male.size(); ++i)
~~^~~~~~~~~~~~~
chameleon.cpp:237:10: warning: unused variable 'ka' [-Wunused-variable]
bool ka=false;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
640 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
640 KB |
Wrong Answer [5] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
640 KB |
Output is correct |
| 3 |
Correct |
5 ms |
640 KB |
Output is correct |
| 4 |
Correct |
5 ms |
512 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
5 ms |
640 KB |
Output is correct |
| 8 |
Correct |
5 ms |
512 KB |
Output is correct |
| 9 |
Correct |
5 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
640 KB |
Output is correct |
| 3 |
Correct |
5 ms |
640 KB |
Output is correct |
| 4 |
Correct |
5 ms |
512 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
5 ms |
640 KB |
Output is correct |
| 8 |
Correct |
5 ms |
512 KB |
Output is correct |
| 9 |
Correct |
5 ms |
640 KB |
Output is correct |
| 10 |
Correct |
7 ms |
640 KB |
Output is correct |
| 11 |
Correct |
6 ms |
512 KB |
Output is correct |
| 12 |
Correct |
6 ms |
640 KB |
Output is correct |
| 13 |
Correct |
6 ms |
512 KB |
Output is correct |
| 14 |
Correct |
6 ms |
640 KB |
Output is correct |
| 15 |
Correct |
6 ms |
640 KB |
Output is correct |
| 16 |
Correct |
6 ms |
640 KB |
Output is correct |
| 17 |
Correct |
6 ms |
512 KB |
Output is correct |
| 18 |
Correct |
6 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
640 KB |
Output is correct |
| 2 |
Correct |
4 ms |
512 KB |
Output is correct |
| 3 |
Correct |
40 ms |
768 KB |
Output is correct |
| 4 |
Correct |
34 ms |
640 KB |
Output is correct |
| 5 |
Correct |
34 ms |
640 KB |
Output is correct |
| 6 |
Correct |
35 ms |
640 KB |
Output is correct |
| 7 |
Correct |
34 ms |
640 KB |
Output is correct |
| 8 |
Correct |
34 ms |
640 KB |
Output is correct |
| 9 |
Correct |
34 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
640 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
640 KB |
Wrong Answer [5] |
| 4 |
Halted |
0 ms |
0 KB |
- |
