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 <bits/stdc++.h>
#include "highway.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 9e4, K = 10;
vector<pair<int, int>> graph[N];
vector<int> ones, zeros;
void dfs(int v, int p, bool flag){
if(flag) ones.push_back(v);
else zeros.push_back(v);
for(auto e : graph[v]){
if(e.first != p){
dfs(e.first, v, flag ^ 1);
}
}
}
void find_pair(int n, vector<int> u, vector<int> v, int a, int b){
int m = u.size(), s = -1, t = -1;
for(int i = 0; i < m; i++){
graph[u[i]].push_back({v[i], i});
graph[v[i]].push_back({u[i], i});
}
vector<int> tmp(m, 0);
long long dist = ask(tmp);
dfs(0, -1, 0);
if(zeros.size() > ones.size()) swap(zeros, ones);
for(auto x : ones) cout << x << " ";
cout << "\n";
for(auto x : zeros) cout << x << " ";
cout << "\n";
tmp.assign(m, 0);
for(auto v : ones){
for(auto e : graph[v]){
tmp[e.second] = 1;
}
}
if(((ask(tmp) - dist) / (b - a)) % 2 == 1){
int l = 0, r = ones.size(), md;
while(r - l > 1){
md = l + (r - l) / 2;
tmp.assign(m, 0);
for(int i = 0; i < md; i++){
int v = ones[i];
for(auto e : graph[v]) tmp[e.second] = 1;
}
if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
else l = md;
}
s = ones[l];
l = 0, r = zeros.size();
while(r - l > 1){
md = l + (r - l) / 2;
tmp.assign(m, 0);
for(int i = 0; i < md; i++){
int v = zeros[i];
for(auto e : graph[v]) tmp[e.second] = 1;
}
if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
else l = md;
}
t = zeros[l];
answer(s, t);
return;
}
else{
for(int it = 0; it < K; it++){
shuffle(ones.begin(), ones.end(), rng);
tmp.assign(m, 0);
for(int i = 0; i <= (ones.size() - 1) / 2; i++){
int v = ones[i];
for(auto e : graph[v]) tmp[e.second] = 1;
}
if(((ask(tmp) - dist) / (b - a)) % 2 == 1){
vector<int> seta, setb;
for(int i = 0; i <= (ones.size() - 1) / 2; i++) seta.push_back(ones[i]);
for(int i = (ones.size() - 1) / 2 + 1; i < ones.size(); i++) setb.push_back(ones[i]);
int l = 0, r = seta.size(), md;
while(r - l > 1){
md = l + (r - l) / 2;
tmp.assign(m, 0);
for(int i = 0; i < md; i++){
int v = seta[i];
for(auto e : graph[v]) tmp[e.second] = 1;
}
if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
else l = md;
}
s = seta[l];
l = 0, r = setb.size();
while(r - l > 1){
md = l + (r - l) / 2;
tmp.assign(m, 0);
for(int i = 0; i < md; i++){
int v = setb[i];
for(auto e : graph[v]) tmp[e.second] = 1;
}
if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
else l = md;
}
t = setb[l];
answer(s, t);
return;
}
}
for(int it = 0; it < K; it++){
shuffle(zeros.begin(), zeros.end(), rng);
tmp.assign(m, 0);
for(int i = 0; i <= (zeros.size() - 1) / 2; i++){
int v = zeros[i];
for(auto e : graph[v]) tmp[e.second] = 1;
}
if(((ask(tmp) - dist) / (b - a)) % 2 == 1){
vector<int> seta, setb;
for(int i = 0; i <= (zeros.size() - 1) / 2; i++) seta.push_back(zeros[i]);
for(int i = (zeros.size() - 1) / 2 + 1; i < zeros.size(); i++) setb.push_back(zeros[i]);
int l = 0, r = seta.size(), md;
while(r - l > 1){
md = l + (r - l) / 2;
tmp.assign(m, 0);
for(int i = 0; i < md; i++){
int v = seta[i];
for(auto e : graph[v]) tmp[e.second] = 1;
}
if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
else l = md;
}
s = seta[l];
l = 0, r = setb.size();
while(r - l > 1){
md = l + (r - l) / 2;
tmp.assign(m, 0);
for(int i = 0; i < md; i++){
int v = setb[i];
for(auto e : graph[v]) tmp[e.second] = 1;
}
if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
else l = md;
}
t = setb[l];
answer(s, t);
return;
}
}
}
assert(false);
}
Compilation message (stderr)
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:104:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i = 0; i <= (ones.size() - 1) / 2; i++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:113:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int i = 0; i <= (ones.size() - 1) / 2; i++) seta.push_back(ones[i]);
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:114:58: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i = (ones.size() - 1) / 2 + 1; i < ones.size(); i++) setb.push_back(ones[i]);
| ~~^~~~~~~~~~~~~
highway.cpp:165:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | for(int i = 0; i <= (zeros.size() - 1) / 2; i++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:174:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | for(int i = 0; i <= (zeros.size() - 1) / 2; i++) seta.push_back(zeros[i]);
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:175:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | for(int i = (zeros.size() - 1) / 2 + 1; i < zeros.size(); i++) setb.push_back(zeros[i]);
| ~~^~~~~~~~~~~~~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |