#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;
}
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);
}
sex[0]=0;
queue<int>yo;
yo.push(0);
while(!yo.empty())
{
auto u=yo.front();
yo.pop();
set<int>ko=unknown;
for(auto it:ko)
{
ve hi;
hi.pb(u+1);hi.pb(it+1);
if(Query(hi)==1)
{
sex[it]=1-sex[u];
yo.push(it);
unknown.erase(it);
}
}
}
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);
//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(cur+1,female[posi1]+1);
Answer(cur+1,female[posi1]+1);
cores[female[posi1]]=cur;
}
posia[female[posi1]].pb(cur);
}
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:83:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < male.size(); ++i)
~~^~~~~~~~~~~~~
chameleon.cpp:104:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(kol==yo.size())
~~~^~~~~~~~~~~
chameleon.cpp:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(kol==yo.size())
~~~^~~~~~~~~~~
chameleon.cpp:143:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(kol==yo.size())
~~~^~~~~~~~~~~
chameleon.cpp:153:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(kol==yo.size())
~~~^~~~~~~~~~~
chameleon.cpp:183:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(kol==yo.size())
~~~^~~~~~~~~~~
chameleon.cpp:193:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(kol==yo.size())
~~~^~~~~~~~~~~
chameleon.cpp:214:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < male.size(); ++i)
~~^~~~~~~~~~~~~
chameleon.cpp:229:17: warning: unused variable 'ko' [-Wunused-variable]
int ko = Query(fa);
^~
chameleon.cpp:252:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < male.size(); ++i)
~~^~~~~~~~~~~~~
chameleon.cpp:213:10: warning: unused variable 'ka' [-Wunused-variable]
bool ka=false;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
640 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
512 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
512 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
640 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
640 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
