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 <bits/stdc++.h>
using namespace std;
bool sex[1005];
vector <int> v[1005];
vector <int> Left, Right;
vector <int> cand[1005];
bool isCandidate(int x, int y, vector <int> v, int val){
vector <int> q;
if(val != -1) q.push_back(val);
for(int i = x; i <= y ; ++i) q.push_back(v[i]);
return Query(q) - q.size();
}
bool find_candidates(int i, vector <int> v){
if(!v.empty()){
while(isCandidate(0, v.size() - 1, v, i)){
if(v.size() == 1){
cand[i].push_back(v[0]);
cand[v[0]].push_back(i);
v.pop_back();
break ;
}
int st = 1, dr = v.size();
while(st <= dr){
int mij = (st + dr) / 2;
if(isCandidate(st - 1, mij - 1, v, i)) dr = mij - 1;
else st = mij + 1;
}
cand[i].push_back(v[st - 1]);
cand[v[st - 1]].push_back(i);
swap(v[st - 1], v[v.size() - 1]);
v.pop_back();
if(v.empty()) break ;
}
}
}
bool viz[1005];
void color(int nod){
viz[nod] = 1;
for(auto it : cand[nod]){
if(viz[it]) continue ;
sex[it] = 1 - sex[nod];
color(it);
}
}
bool match[1005][1005];
bool found[1005];
void Solve(int n){
for(int i = 2; i <= 2 * n ; ++i){
for(int j = 1; j < i ; ++j) viz[j] = 0;
sex[i - 1] = 0;
color(i - 1);
///we find all the chameleons on the left
Left.clear();
for(int j = 1; j < i ; ++j)
if(sex[j] == 0 && cand[j].size() < 3) Left.push_back(j);
find_candidates(i, Left);
if(cand[i].size() == 3) continue ;
///we find all the chameleons on the right
Right.clear();
for(int j = 1; j < i ; ++j)
if(sex[j] == 1 && cand[j].size() < 3) Right.push_back(j);
find_candidates(i, Right);
}
for(int i = 1; i <= 2 * n ; ++i){
if(found[i]) continue ;
if(cand[i].size() == 1){
found[i] = found[cand[i][0]] = true;
Answer(i, cand[i][0]);
continue ;
}
vector <int> v;
for(auto x : cand[i]){
for(auto y : cand[i]){
if(x >= y) continue ;
v.clear();
v.push_back(x);
v.push_back(y);
v.push_back(i);
if(Query(v) == 1){
match[i][x] = 1;
match[i][y] = 1;
break ;
}
}
}
}
for(int i = 1; i <= 2 * n ; ++i){
if(found[i]) continue ;
for(int j = 1; j <= 2 * n ; ++j){
if(found[j]) continue ;
if(match[i][j] && match[j][i]){
found[i] = found[j] = true;
Answer(i, j);
}
}
}
}
Compilation message (stderr)
chameleon.cpp: In function 'bool find_candidates(int, std::vector<int>)':
chameleon.cpp:46:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
# | 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... |