#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) {
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) {
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
longesttrip.cpp: In function 'bool query(std::vector<int>, std::vector<int>)':
longesttrip.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i=0; i<a.size(); i++) A.pb(sh[a[i]]);
| ~^~~~~~~~~
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<b.size(); i++) B.pb(sh[b[i]]);
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
229 ms |
344 KB |
too many calls |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
invalid array |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
invalid array |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
invalid array |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
invalid array |
| 2 |
Halted |
0 ms |
0 KB |
- |
