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 <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(j, a, b) for (int j = a; j >= b; j--)
#include "chameleon.h"
#include <cstdio>
#include <cstdlib>
using namespace std;
vector <int> sub_vector(int b, int e, vector <int>& f){
vector <int> r(e-b);
rep(i,0,e-b){
r[i]=f[i+b];
}
return r;
}
int binary(int s, int ee, int e, vector <int>& curr){
int start=s, end = ee;
while(start!=end-1)
{
int middle = (start+end)/2;
vector <int> sub = sub_vector(middle,e, curr);
int see = Query(sub);
if(sub.size()==see)
end=middle;
else
start=middle;
}
return start;
}
vector <bool> visited;
vector <vector <int> > verti;
vector <pair <int, int> > graph;
void dfs(int p){
vector <int> ch = {0,0,0};
if(graph[p].first!=-1&&graph[p].second!=-1){
return ;
}
rep(i,0,3){
rep(j,i+1,3){
if(i==j)continue;
vector <int> ctry = {p, verti[p][i], verti[p][j]};
if(Query(ctry)==2){
ch[i]++;
ch[j]++;
}
}
}
rep(i,0,3){
if(ch[i]==2){
graph[p].second = verti[p][i];
graph[verti[p][i]].first = p;
dfs(verti[p][i]);
}
}
return ;
}
void Solve(int N) {
int n=N*2;
vector <vector <int> > v(4);
verti.resize(n+1);
visited.assign(n+1,0);
graph.assign(n+1,{-1,-1});
rep(i,1, n+1){
vector <int> curr;
bool flag = false;
rep(j,0,4){
curr = v[j];
curr.push_back(i);
int check = Query(curr);
if(check==curr.size()&& !flag){
v[j].push_back(i);
flag = true;
continue;
}
while(check!=curr.size()){
int remov = binary(0, curr.size(), curr.size(), curr);
verti[i].push_back(curr[remov]);
curr.erase (curr.begin()+remov);
check = Query(curr);
}
}
}
rep(i,1,n+1){
if(visited[i])continue;
if(verti[i].size()==1){
Answer(i,verti[i][0]);
visited[i]=1;
visited[verti[i][0]]=1;
} else if(verti[i].size()>1&& graph[i].first!=-1){
rep(j,0,3){
if(verti[i][j]!=graph[i].first&& verti[i][j]!=graph[i].second){
Answer(i,verti[i][j]);
visited[i]=1;
visited[verti[i][j]]=1;
}
}
} else if(verti[i].size()>1){
dfs(i);
rep(j,0,3){
if(verti[i][j]!=graph[i].first&& verti[i][j]!=graph[i].second){
Answer(i,verti[i][j]);
visited[i]=1;
visited[verti[i][j]]=1;
}
}
}
}
}
Compilation message (stderr)
chameleon.cpp: In function 'int binary(int, int, int, std::vector<int>&)':
chameleon.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(sub.size()==see)
~~~~~~~~~~^~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:80:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(check==curr.size()&& !flag){
~~~~~^~~~~~~~~~~~~
chameleon.cpp:85:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(check!=curr.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... |