#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define ld long double
//#define int short
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define mp make_pair
#define vv vector
#define endl '\n'
#include "chameleon.h"
using namespace std;
bool query(vi all, int extra){
all.pb(extra);
//for(auto e: all)cout << e << " ";cout << endl;
return Query(all) == all.size();
}
int count(vi all, int extra){
all.pb(extra);
return ((int)all.size()) - Query(all);
}
int query3(int a,int b,int c){
vi all;all.pb(a);all.pb(b);all.pb(c);
return Query(all);
}
vi res;
bool ok = 1;
vi edges[1002];
int lst = 0;
void binsrch(vi allNum,int x,int lst = 0){
if(edges[x].size() >= 3)return;
if(allNum.size() == 1){
edges[allNum[0]].pb(x);
edges[x].pb(allNum[0]);
//lst = allNum[0];
return;
}
//cout << allNum.size() << endl;;
vi halves[2];
FOR(i,allNum.size())halves[i%2].pb(allNum[i]);
if(query(halves[0],x)){
binsrch(halves[1],x);
}else{
binsrch(halves[0],x);
if(edges[x].size() < 3 and !query(halves[1],x))binsrch(halves[1],x);
}
}
vi indsets[4];
void Solve(int n){
n*=2;
indsets[0].pb(1);
FORE(i,2,n){
FOR(j,4){
if(indsets[j].empty() or query(indsets[j],i)){
indsets[j].pb(i);
break;
}
}
}
// everything has been partitioned.
FOR(i,4){
for(auto e : indsets[i]){
FOR(j,4){
//while()
if(indsets[j].empty())continue;
if(i != j and !indsets[j].empty()){
ok = 1;
if(query(indsets[j],e))continue;
vi rdlst;
for(auto x:indsets[j])if(x < e)rdlst.pb(x);
binsrch(rdlst,e);
}
}
}
}
FORE(i,1,n){
// cout << edges[i].size() << endl;
}
set<int> allSets[n+1];
FOR(i,n+1)for(auto x:edges[i])allSets[i].insert(x);
FORE(i,1,n){
if(edges[i].size() == 1){
continue;
}
//if(edges[i].size() != 3)while(1);
// has 3 edges;
int a = query3(i,edges[i][0],edges[i][1]);
int b = query3(i,edges[i][1],edges[i][2]);
int numTorem;
if(a == 1){
numTorem = edges[i][2];
}else if(b == 1){
numTorem = edges[i][0];
}else{
numTorem = edges[i][1];
}
allSets[i].erase(numTorem);
allSets[numTorem].erase(i);
}
FORE(i,1,n){
int x = *(allSets[i].begin());
if(i < x)Answer(i,x);
}
}
Compilation message
chameleon.cpp: In function 'bool query(std::vector<int>, int)':
chameleon.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
return Query(all) == all.size();
~~~~~~~~~~~^~~~~~~~~~~~~
chameleon.cpp: In function 'void binsrch(std::vector<int>, int, int)':
chameleon.cpp:18:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i,n) for(int i=0;i<n;i++)
chameleon.cpp:69:6:
FOR(i,allNum.size())halves[i%2].pb(allNum[i]);
~~~~~~~~~~~~~~~
chameleon.cpp:69:2: note: in expansion of macro 'FOR'
FOR(i,allNum.size())halves[i%2].pb(allNum[i]);
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3200 KB |
Wrong Answer [3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3200 KB |
Wrong Answer [3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3200 KB |
Wrong Answer [3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
3156 KB |
Wrong Answer [3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3200 KB |
Wrong Answer [3] |
| 2 |
Halted |
0 ms |
0 KB |
- |
