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>
#define mp make_pair
#define pb push_back
#define pll pair<long long, long long>
#define MOD 1000000007ll
#define xx first
#define yy second
using namespace std;
typedef long long ll;
mt19937 mt(169);
bool are_connected(vector<int> A, vector<int> B);
vector<int> sh;
bool query(vector<int> a, vector<int> b) {
if(a.empty()||b.empty()) while (true);
vector<int> A, B;
for(int i=0; i<a.size(); i++) A.pb(sh[a[i]]);
for(int i=0; i<b.size(); i++) B.pb(sh[b[i]]);
/*for(int i:a) cout<<i<<' ';
cout<<'\n';
for(int i:b) cout<<i<<' ';
cout<<'\n';*/
return are_connected(A, B);
}
int cur, zadnji, sled;
bool nema;
vector<int> put, klika;
int ko(int jedan, vector<int> vise, int l, int r) {
vector<int> a, b;
a.pb(jedan);
int m=(l+r)/2;
for(int i=l; i<=m; i++) b.pb(vise[i]);
if(query(a, b)) return ko(jedan, vise, l, m);
else return ko(jedan, vise, m+1, r);
}
vector<int> vrati(vector<int> v) {
vector<int> rez;
for(int i:v) rez.pb(sh[i]);
return rez;
}
vector<int> longest_trip(int N, int D) {
sh.clear();
for(int i=0; i<N; i++) sh.pb(i);
//shuffle(sh.begin(), sh.end(), mt);
cur=0;
zadnji=0;
klika.clear();
put.clear();
put.pb(0);
vector<int> a, b;
while(zadnji<N-1) {
if(zadnji<cur) while (true);
a.clear();
b.clear();
if(klika.empty()) {
a.pb(cur);
b.pb(zadnji+1);
if(query(a, b)) {
cur=zadnji+1;
put.pb(cur);
zadnji=max(cur, zadnji);
continue;
}
klika.pb(zadnji+1);
zadnji=max(zadnji, klika.back());
nema=true;
}
else {
sled=zadnji+1;
if(nema) {
a.pb(cur);
b.pb(sled);
if(query(a, b)) {
cur=sled;
put.pb(cur);
zadnji=max(cur, zadnji);
nema=false;
}
else {
klika.pb(sled);
zadnji=max(klika.back(), zadnji);
}
continue;
}
a.pb(cur);
a.pb(sled);
if(query(a, klika)) {
a.pop_back();
if(!query(a, klika)) {
cur=sled;
put.pb(cur);
zadnji=max(cur, zadnji);
}
sled=ko(cur, klika, 0, klika.size()-1);
put.pb(sled);
for(int i:klika) {
if(i!=sled) {
put.pb(i);
cur=i;
}
}
klika.clear();
}
}
}
if(query(put, klika)) {
while(true);
}
else {
if(put.size()>klika.size()) return vrati(put);
else return vrati(klika);
}
}
Compilation message (stderr)
longesttrip.cpp: In function 'bool query(std::vector<int>, std::vector<int>)':
longesttrip.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for(int i=0; i<a.size(); i++) A.pb(sh[a[i]]);
| ~^~~~~~~~~
longesttrip.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i=0; i<b.size(); i++) B.pb(sh[b[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... |