#include "chameleon.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
void solve2(int N) {
vector<ll> pa[2*N+5];
for (int i=1;i<=2*N;i++){
for (int j=i+1;j<=2*N;j++){
vector<ll> temp(2);
temp[0] = i;
temp[1] = j;
if (Query(temp)==1) {
pa[i].push_back(j);
pa[j].push_back(i);
}
}
}
ll col[2*N+5];
ll know[2*N+5];
memset(know,0,sizeof(know));
for (int i=1;i<=2*N;i++){
if (know[i]==1) continue;
if (pa[i].size()==1){
col[i] = pa[i][0];
col[pa[i][0]] = i;
know[i] = 1;
know[pa[i][0]] = 1;
continue;
}
ll like=-1;
vector<ll> temp(3);
temp[0] = i;
temp[1] = pa[i][0];
temp[2] = pa[i][1];
if (Query(temp)==1){
like = 2;
}
temp[1] = pa[i][1];
temp[2] = pa[i][2];
if (Query(temp)==1){
like = 0;
}
temp[1] = pa[i][2];
temp[2] = pa[i][0];
if (Query(temp)==1){
like = 1;
}
//cout << i << " " << pa[i][like] << "\n";
ll fail=-1,pass=-1;
for (int j=0;j<3;j++){
if (j==like) continue;
ll x = pa[i][j];
if (know[x]==1) {
fail=j;
break;
}
if (pa[x].size()==1){
if (pa[x][0]==i){
pass=j;
break;
}
else{
fail=j;
break;
}
}
ll like2=-1;
vector<ll> temp2(3);
temp2[0] = x;
temp2[1] = pa[x][0];
temp2[2] = pa[x][1];
if (Query(temp2)==1){
like2 = 2;
}
temp2[1] = pa[x][1];
temp2[2] = pa[x][2];
if (Query(temp2)==1){
like2 = 0;
}
temp2[1] = pa[x][2];
temp2[2] = pa[x][0];
if (Query(temp2)==1){
like2 = 1;
}
//cout << x << " " << pa[x][like2] << "\n";
if (pa[x][like2]==i){
fail=j;
break;
}
else{
pass=j;
break;
}
}
//cout << i << " " << fail << " " << pass << "\n";
if (fail==-1){
col[i] = pa[i][pass];
col[pa[i][pass]] = i;
know[i] = 1;
know[pa[i][pass]] = 1;
}
else{
for (int j=0;j<3;j++){
if (j==like || j==fail) continue;
col[i] = pa[i][j];
col[pa[i][j]] = i;
know[i] = 1;
know[pa[i][j]] = 1;
}
}
}
ll out[2*N+5];
memset(out,0,sizeof(out));
for (int i = 1; i <= 2*N; i++) {
if (out[i]==1) continue;
//cout << i << " " << col[i] << "\n";
Answer(i,col[i]);
out[i]=1;
out[col[i]]=1;
}
}
void Solve(int N) {
if (N==50) {
solve2(N);
}
else{
/*
vector<ll> g1,g2,nt;
for (int i=2;i<=2*N;i++){
nt.push(i);
}
g1.push(1);
ll l=1,r=nt.size();
while (l<r){
ll m = l+(r-l)/2;
vector<ll> temp;
temp.push_back(i);
for (int k=l;k<=m;k++){
if (find(used.begin(),used.end(),nt[k])!=used.end()) continue;
temp.push_back(nt[k]);
}
if (Query(temp)!=temp.size()){
r=m;
}
else{
l=m+1;
}
temp.clear();
}
*/
ll found[2*N+5];
memset(found,0,sizeof(found));
vector<ll> pa[2*N+5];
for (int i=1;i<2*N;i++){
if (found[i]==1) continue;
vector<ll> used;
for (int j=0;j<3;j++){
if (j!=used.size()) continue;
ll l=i+1,r=2*N;
while (l<r){
ll m = l+(r-l)/2;
vector<ll> temp,temp2;
temp.push_back(i);
for (int k=l;k<=m;k++){
if (find(used.begin(),used.end(),k)!=used.end()) continue;
temp.push_back(k);
temp2.push_back(k);
}
ll q1 = Query(temp);
if (q1!=temp.size()){
if (Query(temp2)==q1) r=m;
else l=m+1;
}
else{
l=m+1;
}
temp.clear();
temp2.clear();
}
vector<ll> tem;
tem.push_back(l);
tem.push_back(i);
if (find(used.begin(),used.end(),l)!=used.end() || Query(tem)==2) continue;
//cout << i << " " << l << "\n";
pa[i].push_back(l);
pa[l].push_back(i);
used.push_back(l);
}
if (used.size()==1) {
found[i]=1;
found[used[0]]=1;
}
}
/*
for (int i=1;i<=2*N;i++){
cout << i << ": ";
for (auto item:pa[i]) cout << item << " ";
cout << "\n";
cout << i << ": " << found[i] << "\n";
}
cout << "\n";
*/
//for (auto item:pa[1]) cout << item << " ";
//cout << "\n";
ll fail=0;
for (int i=1;i<=2*N;i++){
if (found[i]!=1) fail=1;
}
if (fail==1){
for (int i=1;i<=2*N;i++){
pa[i].clear();
}
for (int i=1;i<=N;i++){
vector<ll> used;
for (int j=0;j<3;j++){
ll l=N+1,r=2*N;
while (l<r){
ll m = l+(r-l)/2;
vector<ll> temp;
temp.push_back(i);
for (int k=l;k<=m;k++){
if (find(used.begin(),used.end(),k)!=used.end()) continue;
temp.push_back(k);
}
if (Query(temp)!=temp.size()){
r=m;
}
else{
l=m+1;
}
temp.clear();
}
vector<ll> tem;
tem.push_back(l);
tem.push_back(i);
if (find(used.begin(),used.end(),l)!=used.end() || Query(tem)==2) continue;
//cout << i << " " << l << "\n";
pa[i].push_back(l);
pa[l].push_back(i);
used.push_back(l);
}
}
}
//cout << "a";
ll col[2*N+5];
ll know[2*N+5];
memset(know,0,sizeof(know));
for (int i=1;i<=2*N;i++){
//cout << i << ": ";
//for (auto item:pa[i]) cout << item << " ";
//cout << "\n";
if (know[i]==1) continue;
if (pa[i].size()==1){
col[i] = pa[i][0];
col[pa[i][0]] = i;
know[i] = 1;
know[pa[i][0]] = 1;
continue;
}
ll like=-1;
vector<ll> temp(3);
temp[0] = i;
temp[1] = pa[i][0];
temp[2] = pa[i][1];
if (Query(temp)==1){
like = 2;
}
temp[1] = pa[i][1];
temp[2] = pa[i][2];
if (Query(temp)==1){
like = 0;
}
temp[1] = pa[i][2];
temp[2] = pa[i][0];
if (Query(temp)==1){
like = 1;
}
//cout << i << " " << pa[i][like] << "\n";
ll fail=-1,pass=-1;
for (int j=0;j<3;j++){
if (j==like) continue;
ll x = pa[i][j];
if (know[x]==1) {
fail=j;
break;
}
if (pa[x].size()==1){
if (pa[x][0]==i){
pass=j;
break;
}
else{
fail=j;
break;
}
}
ll like2=-1;
vector<ll> temp2(3);
temp2[0] = x;
temp2[1] = pa[x][0];
temp2[2] = pa[x][1];
if (Query(temp2)==1){
like2 = 2;
}
temp2[1] = pa[x][1];
temp2[2] = pa[x][2];
if (Query(temp2)==1){
like2 = 0;
}
temp2[1] = pa[x][2];
temp2[2] = pa[x][0];
if (Query(temp2)==1){
like2 = 1;
}
//cout << x << " " << pa[x][like2] << "\n";
if (pa[x][like2]==i){
fail=j;
break;
}
else{
pass=j;
break;
}
}
//cout << i << " " << fail << " " << pass << "\n";
if (fail==-1){
col[i] = pa[i][pass];
col[pa[i][pass]] = i;
know[i] = 1;
know[pa[i][pass]] = 1;
}
else{
for (int j=0;j<3;j++){
if (j==like || j==fail) continue;
col[i] = pa[i][j];
col[pa[i][j]] = i;
know[i] = 1;
know[pa[i][j]] = 1;
}
}
}
ll out[2*N+5];
memset(out,0,sizeof(out));
for (int i = 1; i <= 2*N; i++) {
if (out[i]==1) continue;
//cout << i << " " << col[i] << "\n";
Answer(i,col[i]);
out[i]=1;
out[col[i]]=1;
}
}
}
Compilation message
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:163:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | if (j!=used.size()) continue;
| ~^~~~~~~~~~~~~
chameleon.cpp:175:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | if (q1!=temp.size()){
| ~~^~~~~~~~~~~~~
chameleon.cpp:232:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
232 | if (Query(temp)!=temp.size()){
| ~~~~~~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
21 ms |
344 KB |
Output is correct |
| 4 |
Correct |
24 ms |
484 KB |
Output is correct |
| 5 |
Correct |
21 ms |
484 KB |
Output is correct |
| 6 |
Correct |
21 ms |
344 KB |
Output is correct |
| 7 |
Correct |
21 ms |
344 KB |
Output is correct |
| 8 |
Correct |
21 ms |
344 KB |
Output is correct |
| 9 |
Correct |
21 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [5] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [5] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
28 ms |
344 KB |
Wrong Answer [3] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
21 ms |
344 KB |
Output is correct |
| 4 |
Correct |
24 ms |
484 KB |
Output is correct |
| 5 |
Correct |
21 ms |
484 KB |
Output is correct |
| 6 |
Correct |
21 ms |
344 KB |
Output is correct |
| 7 |
Correct |
21 ms |
344 KB |
Output is correct |
| 8 |
Correct |
21 ms |
344 KB |
Output is correct |
| 9 |
Correct |
21 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [5] |
| 12 |
Halted |
0 ms |
0 KB |
- |
