#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll n,i,j,k,s,t,x,y,z,w;
deque<ll> dq1,dq2;
vector<ll>v;
pair<ll,ll> p;
pair<ll,ll> inv(pair<ll,ll> p)
{
return {p.second,p.first};
}
pair<ll,ll> adj(vector<ll> a,vector<ll> b)
{
ll k=0;
if(a.size()<b.size())
{swap(a,b); k=1;}
if(a.size()==1&&b.size()==1)
return {a[0],b[0]};
vector<ll>c;
for(i=0;i<a.size()/2;i++)
c.push_back(a[i]);
if(are_connected(c,b))
{
if(k==1)
{
return inv(adj(c,b));
}
else
return adj(c,b);
}
else
{
c.clear();
for(i=a.size()/2;i<a.size();i++)
c.push_back(a[i]);
if(k==1)
{
return inv(adj(c,b));
}
else
return adj(c,b);
}
}
vector<ll> vectorize(deque<ll> d)
{
ll i;
vector<ll> v;
for(i=0;i<d.size();i++)
v.push_back(d[i]);
return v;
}
void combine()
{
for(auto x:dq2)
dq1.push_front(x);
dq2.clear();
}
void answer()
{
ll i;
v.clear();
for(i=0;i<dq1.size();i++)
{
v.push_back(dq1[i]);
}
}
void init()
{
dq1.clear();
dq2.clear();
v.clear();
s=0;
t=0;
}
vector<ll> longest_trip(ll N, ll D)
{
init();
n=N;
dq1.push_back(0);
dq2.push_back(1);
for(i=2;i<n;i++)
{
if(i==n-1)
{if(are_connected({dq1[0]},{dq2[0]}))
{
combine();
dq2.push_back(i);
continue;
}
if(are_connected({dq1[0]},{i}))
{
dq1.push_front(i);
continue;
}
dq2.push_front(i);
}
else
{
if(are_connected({i},{i+1}))
{
if(are_connected({dq1[0]},{dq2[0]}))
{
combine();
dq2.push_back(i);
dq2.push_back(i+1);
i++;
continue;
}
if(are_connected({dq1[0]},{i}))
{
dq1.push_front(i);
dq1.push_front(i+1);
i++;
continue;
}
dq2.push_front(i);
dq2.push_front(i+1);
}
else
{
if(are_connected({dq1[0]},{i}))
{
dq1.push_front(i);
if(are_connected({dq2[0]},{i}))
{
combine();
dq2.push_back(i+1);
}
else
{
dq2.push_front(i+1);
}
}
else
{
dq2.push_front(i);
if(are_connected({dq1[0]},{i}))
{
combine();
dq2.push_back(i+1);
}
else
{
dq1.push_front(i+1);
}
}
}
i++;
}
}
if(dq1.size()<dq2.size())
swap(dq1,dq2);
if(!are_connected(vectorize(dq1),vectorize(dq2)))
{
answer();
return v;
}
/*for(ll x:dq1)
printf("%d ",x);
printf("\n");
for(ll x:dq2)
printf("%d ",x);
printf("\n");*/
if(dq2.size()==1)
{
if(are_connected({dq1[0]},{dq2[0]}))
{
dq1.push_front(dq2[0]);
}
else if(are_connected({dq1[dq1.size()-1]},{dq2[0]}))
{
dq1.push_back(dq2[0]);
}
else
{
for(i=0;i<dq1.size();i++)
{
v.push_back(dq1[i]);
}
x=adj(vectorize(dq1),vectorize(dq2)).first;
v.clear();
v.push_back(dq2[0]);
for(i=0;i<dq1.size();i++)
{
if(dq1[i]==x)
{
t=1;
}
if(t==1)
v.push_back(dq1[i]);
}
for(i=0;i<dq1.size();i++)
{
if(dq1[i]==x)
t=0;
if(t==1)
v.push_back(dq1[i]);
}
return v;
}
answer();
return v;
}
if(are_connected({dq1[0]},{dq2[0]}))
{
for(auto x:dq2)
dq1.push_front(x);
answer();
return v;
}
else if(are_connected({dq1[0]},{dq2[dq2.size()-1]}))
{
for(i=dq2.size()-1;i>=0;i--)
{
dq1.push_front(dq2[i]);
}
answer();
return v;
}
else if(are_connected({dq1[dq1.size()-1]},{dq2[0]}))
{
for(auto x:dq2)
dq1.push_back(x);
answer();
return v;
}
else if(are_connected({dq1[dq1.size()-1]},{dq2[dq2.size()-1]}))
{
for(i=dq2.size()-1;i>=0;i--)
{
dq1.push_back(dq2[i]);
}
answer();
return v;
}
else
{
p=adj(vectorize(dq1),vectorize(dq2));
x=p.first;
y=p.second;
//printf("%d %d\n",x,y);
t=0;
for(i=0;i<dq1.size();i++)
{
if(t==1)
{
v.push_back(dq1[i]);
}
if(dq1[i]==x)
t=1;
}
for(i=0;i<dq1.size();i++)
{
if(t==1)
v.push_back(dq1[i]);
if(dq1[i]==x)
t=0;
}
for(i=0;i<dq2.size();i++)
{
if(dq2[i]==y)
t=1;
if(t==1)
{
v.push_back(dq2[i]);
}
}
for(i=0;i<dq2.size();i++)
{
if(dq2[i]==y)
t=0;
if(t==1)
v.push_back(dq2[i]);
}
return v;
}
}
Compilation message
longesttrip.cpp: In function 'std::pair<int, int> adj(std::vector<int>, std::vector<int>)':
longesttrip.cpp:21:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(i=0;i<a.size()/2;i++)
| ~^~~~~~~~~~~
longesttrip.cpp:35:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(i=a.size()/2;i<a.size();i++)
| ~^~~~~~~~~
longesttrip.cpp: In function 'std::vector<int> vectorize(std::deque<int>)':
longesttrip.cpp:49:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(i=0;i<d.size();i++)
| ~^~~~~~~~~
longesttrip.cpp: In function 'void answer()':
longesttrip.cpp:63:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(i=0;i<dq1.size();i++)
| ~^~~~~~~~~~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(ll, ll)':
longesttrip.cpp:152:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
152 | if(dq1.size()<dq2.size())
| ^~
longesttrip.cpp:154:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
154 | if(!are_connected(vectorize(dq1),vectorize(dq2)))
| ^~
longesttrip.cpp:177:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | for(i=0;i<dq1.size();i++)
| ~^~~~~~~~~~~
longesttrip.cpp:184:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
184 | for(i=0;i<dq1.size();i++)
| ~^~~~~~~~~~~
longesttrip.cpp:193:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
193 | for(i=0;i<dq1.size();i++)
| ~^~~~~~~~~~~
longesttrip.cpp:244:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
244 | for(i=0;i<dq1.size();i++)
| ~^~~~~~~~~~~
longesttrip.cpp:253:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
253 | for(i=0;i<dq1.size();i++)
| ~^~~~~~~~~~~
longesttrip.cpp:260:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
260 | for(i=0;i<dq2.size();i++)
| ~^~~~~~~~~~~
longesttrip.cpp:269:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
269 | for(i=0;i<dq2.size();i++)
| ~^~~~~~~~~~~
longesttrip.cpp:271:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
271 | if(dq2[i]==y)
| ^~
longesttrip.cpp:273:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
273 | if(t==1)
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
344 KB |
Output is correct |
| 2 |
Correct |
6 ms |
344 KB |
Output is correct |
| 3 |
Correct |
4 ms |
344 KB |
Output is correct |
| 4 |
Correct |
6 ms |
436 KB |
Output is correct |
| 5 |
Correct |
5 ms |
440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
344 KB |
Output is correct |
| 2 |
Correct |
7 ms |
344 KB |
Output is correct |
| 3 |
Correct |
5 ms |
596 KB |
Output is correct |
| 4 |
Correct |
5 ms |
344 KB |
Output is correct |
| 5 |
Correct |
6 ms |
856 KB |
Output is correct |
| 6 |
Correct |
11 ms |
344 KB |
Output is correct |
| 7 |
Correct |
7 ms |
344 KB |
Output is correct |
| 8 |
Correct |
5 ms |
340 KB |
Output is correct |
| 9 |
Correct |
5 ms |
600 KB |
Output is correct |
| 10 |
Correct |
5 ms |
452 KB |
Output is correct |
| 11 |
Correct |
4 ms |
344 KB |
Output is correct |
| 12 |
Correct |
5 ms |
344 KB |
Output is correct |
| 13 |
Correct |
4 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
344 KB |
Output is correct |
| 2 |
Correct |
5 ms |
344 KB |
Output is correct |
| 3 |
Correct |
4 ms |
344 KB |
Output is correct |
| 4 |
Correct |
5 ms |
344 KB |
Output is correct |
| 5 |
Correct |
4 ms |
344 KB |
Output is correct |
| 6 |
Correct |
8 ms |
344 KB |
Output is correct |
| 7 |
Correct |
8 ms |
344 KB |
Output is correct |
| 8 |
Correct |
4 ms |
600 KB |
Output is correct |
| 9 |
Correct |
4 ms |
344 KB |
Output is correct |
| 10 |
Correct |
5 ms |
344 KB |
Output is correct |
| 11 |
Correct |
4 ms |
344 KB |
Output is correct |
| 12 |
Correct |
5 ms |
600 KB |
Output is correct |
| 13 |
Correct |
5 ms |
344 KB |
Output is correct |
| 14 |
Correct |
6 ms |
344 KB |
Output is correct |
| 15 |
Incorrect |
0 ms |
344 KB |
Incorrect |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
344 KB |
Output is correct |
| 2 |
Correct |
6 ms |
344 KB |
Output is correct |
| 3 |
Correct |
5 ms |
344 KB |
Output is correct |
| 4 |
Correct |
5 ms |
600 KB |
Output is correct |
| 5 |
Correct |
4 ms |
344 KB |
Output is correct |
| 6 |
Correct |
7 ms |
344 KB |
Output is correct |
| 7 |
Correct |
5 ms |
344 KB |
Output is correct |
| 8 |
Correct |
4 ms |
344 KB |
Output is correct |
| 9 |
Correct |
5 ms |
600 KB |
Output is correct |
| 10 |
Correct |
5 ms |
344 KB |
Output is correct |
| 11 |
Correct |
5 ms |
344 KB |
Output is correct |
| 12 |
Correct |
4 ms |
344 KB |
Output is correct |
| 13 |
Correct |
4 ms |
344 KB |
Output is correct |
| 14 |
Correct |
7 ms |
596 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
600 KB |
Incorrect |
| 16 |
Halted |
0 ms |
0 KB |
- |
