#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define sz size()
#define all(x) (x).begin(), (x).end()
vector<int> v1,v2;
vector<int> go(ll x, ll y)
{
if(x) reverse(all(v1));
if(y) reverse(all(v2));
for(int i = 0; i < v2.sz; i++) v1.push_back(v2[i]);
return v1;
}
std::vector<int> longest_trip(int N, int D)
{
mt19937 rnd(time(0));
v1.clear(); v2.clear();
v1.push_back(0);
for(int i = 1; i < N; i++)
{
ll j = rnd()%2;
if(j==0) swap(v1,v2);
bool bo = are_connected({v1.back()},{i});
if(bo==1) v1.push_back(i);
else
{
if(v2.sz==0) v2.push_back(i);
else
{
bo = are_connected({v2.back()},{i});
if(bo==1) v2.push_back(i);
else
{
reverse(all(v2));
for(int j = 0; j < v2.sz; j++) v1.push_back(v2[j]); v2.clear();
v2.push_back(i);
}
}
}
}
if(v2.sz==0) return v1;
if(v1.sz==0) return v2;
//if(v1.sz>v2.sz) return v1; else return v2;
bool b1 = are_connected({v1[0]},{v2[0]});
bool b2 = are_connected({v1[0]},{v2.back()});
bool b3 = are_connected({v1.back()},{v2[0]});
bool b4 = are_connected({v1.back()},{v2.back()});
if(b1)
{
return go(1,0);
}
else if(b2)
{
return go(1,1);
}
else if(b3)
{
return go(0,0);
}
else if(b4)
{
return go(0,1);
}
// not connecteed
bool both = are_connected(v1,v2);
if(both==0)
{
if(v1.sz>v2.sz) return v1; else return v2;
}
// connected
ll l = 0, r = v1.sz-1;
while(l<r)
{
ll mid = (l+r)/2;
vector<int> vv;
for(int i = l; i <= mid; i++) vv.push_back(v1[i]);
bool m = are_connected(vv,v2);
if(m) r = mid; else l = mid+1;
}
ll node1 = l;
l = 0, r = v2.sz-1;
while(l<r)
{
ll mid = (l+r)/2;
vector<int> vv;
for(int i = l; i <= mid; i++) vv.push_back(v2[i]);
bool m = are_connected(vv,{v1[node1]});
if(m) r = mid; else l = mid+1;
}
ll node2 = l;
vector<int> ans;
for(int i = node1+1; i < v1.sz; i++) ans.push_back(v1[i]);
for(int i = 0; i <= node1; i++) ans.push_back(v1[i]);
for(int i = node2; i < v2.sz; i++) ans.push_back(v2[i]);
for(int i = 0; i < node2; i++) ans.push_back(v2[i]);
return ans;
}
Compilation message
longesttrip.cpp: In function 'std::vector<int> go(ll, ll)':
longesttrip.cpp:15:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for(int i = 0; i < v2.sz; i++) v1.push_back(v2[i]);
| ^
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:39:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int j = 0; j < v2.sz; j++) v1.push_back(v2[j]); v2.clear();
| ^
longesttrip.cpp:39:21: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
39 | for(int j = 0; j < v2.sz; j++) v1.push_back(v2[j]); v2.clear();
| ^~~
longesttrip.cpp:39:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
39 | for(int j = 0; j < v2.sz; j++) v1.push_back(v2[j]); v2.clear();
| ^~
longesttrip.cpp:97:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = node1+1; i < v1.sz; i++) ans.push_back(v1[i]);
| ^
longesttrip.cpp:99:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = node2; i < v2.sz; i++) ans.push_back(v2[i]);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
504 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
