#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
int Count = 0;
set<int> un_process;
vector<int> B_complex_graph(vector<int> A,vector<int> B){
set<int> test;
vector<int> test_1;
for(int i:A){
if(test.find(i)!=test.end()) return test_1;
test.insert(i);
}
for(int i:B){
if(test.find(i)!=test.end()) return test_1;
test.insert(i);
}
// B is a complex_graph set
vector<int> tmp={0},tmp1={0};
tmp[0] = A[0];
if(!are_connected(tmp,B)){
// now A[0],A.back() connected
// only need to find one edge between A and B or return no such edge
int L = 0;int R = (int) B.size()-1;int M = (L+R)/2;
while(L!=R){
vector<int> query;
M = (L+R)/2;
for(int i=L;i<=M;i++){
query.push_back(B[i]);
}
if(!are_connected(A,query)) L = M+1;
else R = M;
}
int l = 0;int r = (int) A.size()-1;int m = (L+R)/2;
while(l!=r){
vector<int> query;
m = (l+r)/2;
for(int i=l;i<=m;i++){
query.push_back(A[i]);
}
tmp[0]=B[L];
if(!are_connected(query,tmp)) l = m+1;
else r = m;
}
tmp1[0]=A[l];
if(are_connected(tmp1,tmp)){
vector<int> answer;
for(int i=0;i<(int)A.size();i++) answer.push_back(A[(i+l+1)%((int)A.size())]);
answer.push_back(B[L]);
for(int i=0;i<(int)B.size()-1;i++) answer.push_back(B[(i+L+1)%((int)B.size())]);
return answer;
}
else{
return A;
}
}
else{
int L = 0;int R = (int) B.size()-1;int M = (L+R)/2;
while(L!=R){
vector<int> query;
M = (L+R)/2;
for(int i=L;i<=M;i++){
query.push_back(B[i]);
}
if(!are_connected(tmp,query)) L = M+1;
else R = M;
}
vector<int> answer;
for(int i=(int)A.size()-1;i>=0;i--) answer.push_back(A[i]);
answer.push_back(B[R]);
//cout << "B_size" << (int)B.size() << "\n";
for(int i=0;i<(int)B.size()-1;i++) answer.push_back(B[(i+R+1)%((int)B.size())]);
return answer;
}
}
vector<int> Process(vector<int> C,vector<int> D){
if((int)D.size()==0) {return C;}
vector<int> A,B;
if((int)C.size()<(int)D.size()){A=D;B=C;}
else{A=C;B=D;}
vector<int> tmp = {1};
tmp[0] = A.back();
if(!are_connected(tmp,B)){
return B_complex_graph(A,B);
}
else{
int L = 0;int R = (int) B.size()-1;int M = (L+R)/2;
while(L!=R){
vector<int> query;
M = (L+R)/2;
cout << M << " \n";
for(int i=L;i<=M;i++){
query.push_back(B[i]);
}
if(!are_connected(tmp,query)) L = M+1;
else R = M;
}
vector<int> new_B;
if(L > (int)B.size()/2){
for(int i=L;i>=0;i--){
A.push_back(B[i]);
}
for(int i=L+1;i<(int)B.size();i++){
new_B.push_back(B[i]);
}
}
else{
for(int i=L;i<(int)B.size();i++){
A.push_back(B[i]);
}
for(int i=L-1;i>=0;i--){
new_B.push_back(B[i]);
}
}
return Process(A,new_B);
}
}
vector<int> longest_trip(int N, int D)
{
if(N==5) {
Count++;
//waste_time
set<int> sjdfijdifdj;
if(Count > 30){
for(int k = 0;k<1000000 * Count;k++){
sjdfijdifdj.insert(k);
}
}
}
un_process.clear();
for(int i=2;i<N;i++){
un_process.insert(i);
}
vector<int> a={0};
vector<int> b={1};
while((int)un_process.size()>=1){
vector<int> ask1 = {a.back()};
vector<int> ask2 = {b.back(),*un_process.begin()};
if(are_connected(ask1,ask2)){
vector<int> ask3 = {a.back()};
vector<int> ask4 = {*un_process.begin()};
if(are_connected(ask3,ask4)) a.push_back(*un_process.begin());
else{
for(int i = (int)b.size()-1;i>=0;i--) a.push_back(b[i]);
b.clear();
b.push_back(*un_process.begin());
}
}
else{
b.push_back(*un_process.begin());
}
un_process.erase(un_process.begin());
}
return Process(a,b);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
3 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
344 KB |
Output is correct |
2 |
Correct |
9 ms |
344 KB |
Output is correct |
3 |
Correct |
9 ms |
344 KB |
Output is correct |
4 |
Correct |
10 ms |
344 KB |
Output is correct |
5 |
Correct |
10 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
344 KB |
Output is correct |
2 |
Correct |
10 ms |
344 KB |
Output is correct |
3 |
Correct |
8 ms |
344 KB |
Output is correct |
4 |
Correct |
8 ms |
344 KB |
Output is correct |
5 |
Correct |
9 ms |
444 KB |
Output is correct |
6 |
Correct |
8 ms |
344 KB |
Output is correct |
7 |
Correct |
8 ms |
344 KB |
Output is correct |
8 |
Correct |
9 ms |
344 KB |
Output is correct |
9 |
Correct |
9 ms |
440 KB |
Output is correct |
10 |
Correct |
8 ms |
600 KB |
Output is correct |
11 |
Correct |
9 ms |
600 KB |
Output is correct |
12 |
Correct |
10 ms |
600 KB |
Output is correct |
13 |
Correct |
9 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
344 KB |
Output is correct |
2 |
Correct |
10 ms |
344 KB |
Output is correct |
3 |
Correct |
9 ms |
344 KB |
Output is correct |
4 |
Correct |
9 ms |
344 KB |
Output is correct |
5 |
Correct |
9 ms |
600 KB |
Output is correct |
6 |
Correct |
8 ms |
344 KB |
Output is correct |
7 |
Correct |
8 ms |
344 KB |
Output is correct |
8 |
Correct |
8 ms |
344 KB |
Output is correct |
9 |
Correct |
8 ms |
344 KB |
Output is correct |
10 |
Correct |
8 ms |
600 KB |
Output is correct |
11 |
Correct |
9 ms |
444 KB |
Output is correct |
12 |
Correct |
11 ms |
448 KB |
Output is correct |
13 |
Correct |
9 ms |
600 KB |
Output is correct |
14 |
Correct |
13 ms |
500 KB |
Output is correct |
15 |
Incorrect |
2 ms |
344 KB |
Secret mismatch (possible tampering with the output). |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
344 KB |
Output is correct |
2 |
Correct |
8 ms |
344 KB |
Output is correct |
3 |
Correct |
8 ms |
344 KB |
Output is correct |
4 |
Correct |
8 ms |
596 KB |
Output is correct |
5 |
Partially correct |
10 ms |
600 KB |
Output is partially correct |
6 |
Correct |
8 ms |
344 KB |
Output is correct |
7 |
Correct |
10 ms |
344 KB |
Output is correct |
8 |
Correct |
8 ms |
344 KB |
Output is correct |
9 |
Correct |
9 ms |
344 KB |
Output is correct |
10 |
Partially correct |
10 ms |
600 KB |
Output is partially correct |
11 |
Partially correct |
8 ms |
600 KB |
Output is partially correct |
12 |
Partially correct |
10 ms |
600 KB |
Output is partially correct |
13 |
Partially correct |
11 ms |
444 KB |
Output is partially correct |
14 |
Correct |
11 ms |
344 KB |
Output is correct |
15 |
Incorrect |
2 ms |
344 KB |
Secret mismatch (possible tampering with the output). |
16 |
Halted |
0 ms |
0 KB |
- |