This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "chameleon.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
void Solve(int N) {
vector<ll> pa[2*N+5];
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);
}
}
ll col[2*N+5];
ll know[2*N+5];
memset(know,0,sizeof(know));
for (int i=1;i<=2*N;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 (stderr)
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | if (Query(temp)!=temp.size()){
| ~~~~~~~~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |