oj.uz

Submission #841857

# Submission time Handle Problem Language Result Execution time Memory
841857 2023-09-02T07:41:46 Z anhduc2701 Longest Trip (IOI23_longesttrip) C++17
100 / 100
 15 ms 856 KB 
#include<bits/stdc++.h>
#include "longesttrip.h"
#define pb push_back
#define fi first
#define se second 
using namespace std;
typedef long long ll;
int n;
pair<int,int> getpos(vector<int>A,vector<int>B){
	if(A.size()==1 && B.size()==1){
		return {A[0],B[0]};
	}
	else{
		int mid1=((int)(A.size())-1)/2;
		vector<int>X;
		for(int i=0;i<=mid1;i++){
			X.pb(A[i]);
		}
		if(A.size() > 1 && !are_connected(X,B)){
			X.clear();
			for(int i=mid1+1;i<(int)A.size();i++){
				X.pb(A[i]);
			}
		}
		int mid2=((int)(B.size())-1)/2;
		vector<int>Y;
		for(int i=0;i<=mid2;i++){
			Y.pb(B[i]);
		}
		if(B.size() ==1 || (are_connected(X,Y))){
			return getpos(X,Y);
		}
		else{
			Y.clear();
			for(int i=mid2+1;i<(int)B.size();i++){
				Y.pb(B[i]);
			}
			return getpos(X,Y);
		}
	}
}
vector<int> longest_trip(int N,int D){
	n=N;
	if(D==3){
		vector<int>K;
		for(int i=0;i<N;i++){
			K.pb(i);
		}
		return K;
	}
	else if(D==2){
		vector<int>K;
		if(are_connected(vector<int>(1,0),vector<int>(1,1))){
			K.pb(0);
			K.pb(1);
		}
		else{
			K.pb(0);
			K.pb(2);
			K.pb(1);
		}
		while((int)(K.size())<N){
			int i=(int)(K.size());
			if(are_connected(vector<int>(1,K[0]),vector<int>(1,i))){
				K.insert(K.begin(),i);
			}
			else{
				K.pb(i);
			}
		}
		return K;
	}
	else{
		vector<int>Line1;
		vector<int>Line2;
		Line1.pb(0);
		Line2.pb(1);
		int j=2;
		while(j<N){
			if(j+2<=N){
				if(are_connected(vector<int>(1,Line2.back()),vector<int>(1,j))){
					Line2.pb(j);
					j++;
				}
				else{
					bool d=are_connected(vector<int>(1,j),vector<int>(1,j+1));
					if(d==0){
						Line2.pb(j+1);
						bool d1=are_connected(vector<int>(1,j),vector<int>(1,Line1.back()));
						if(d1==1){
							Line1.pb(j);
						}
						else{
							reverse(Line1.begin(),Line1.end());
							for(auto v:Line1){
								Line2.pb(v);
							}
							Line1.clear();
							Line1.pb(j);
						}
						j+=2;
					}
					else{
						if(are_connected(vector<int>(1,Line1.back()),vector<int>(1,j))){
							Line1.pb(j);
							Line1.pb(j+1);
							j+=2;
						}
						else{
							reverse(Line1.begin(),Line1.end());
							for(auto v:Line1){
								Line2.pb(v);
							}
							Line1.clear();
							Line1.pb(j);
							Line1.pb(j+1);
							j+=2;
						}
					}
				}
			}
			else{
				if(are_connected(vector<int>(1,Line2.back()),vector<int>(1,j))){
					Line2.pb(j);
					j++;
				}
				else if(are_connected(vector<int>(1,Line1.back()),vector<int>(1,j))){
					Line1.pb(j);
					j++;
				}
				else{
					reverse(Line1.begin(),Line1.end());
					for(auto v:Line1){
						Line2.pb(v);
					}
					Line1.clear();
					Line1.pb(j);
					j++;
				}
			}
		}
		if(are_connected(vector<int>(1,Line1.back()),vector<int>(1,Line2.back()))){
			reverse(Line1.begin(),Line1.end());
			for(auto v:Line1){
				Line2.pb(v);
			}
			Line1.clear();
			return Line2;
		}
		else if(are_connected(vector<int>(1,Line1.back()),vector<int>(1,Line2[0]))){
			for(auto v:Line2){
				Line1.pb(v);
			}
			Line2.clear();
			return Line1;
		}
		else if(are_connected(vector<int>(1,Line1[0]),vector<int>(1,Line2.back()))){
			for(auto v:Line1){
				Line2.pb(v);
			}
			Line1.clear();
			return Line2;
		}
		else if(are_connected(vector<int>(1,Line1[0]),vector<int>(1,Line2[0]))){
			reverse(Line2.begin(),Line2.end());
			for(auto v:Line1){
				Line2.pb(v);
			}
			Line1.clear();
			return Line2;
		}
		else{
			if(are_connected(Line1,Line2)){
				pair<int,int>g=getpos(Line1,Line2);
				vector<int>ans;
				for(int i=0;i<(int)(Line1.size());i++){
					if(Line1[i]==g.fi){
						for(int j=i+1;j<(int)(Line1.size());j++){
							ans.pb(Line1[j]);
						}
						for(int j=0;j<=i;j++){
							ans.pb(Line1[j]);
						}
					}
				}
				for(int i=0;i<(int)Line2.size();i++){
					if(Line2[i]==g.se){
						for(int j=i;j<(int)(Line2.size());j++){
							ans.pb(Line2[j]);
						}
						for(int j=0;j<i;j++){
							ans.pb(Line2[j]);
						}
					}
				}
				return ans;
			}
			else{
				if(Line1.size()>Line2.size()){
					return Line1;
				}
				else{
					return Line2;
				}
			}
		}
	}
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 5 ms 436 KB Output is correct
12 Correct 6 ms 852 KB Output is correct
13 Correct 6 ms 600 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 6 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 4 ms 600 KB Output is correct
13 Correct 5 ms 340 KB Output is correct
14 Correct 15 ms 344 KB Output is correct
15 Correct 9 ms 344 KB Output is correct
16 Correct 7 ms 344 KB Output is correct
17 Correct 6 ms 344 KB Output is correct
18 Correct 6 ms 600 KB Output is correct
19 Correct 5 ms 600 KB Output is correct
20 Correct 5 ms 344 KB Output is correct
21 Correct 5 ms 344 KB Output is correct
22 Correct 5 ms 344 KB Output is correct
23 Correct 5 ms 344 KB Output is correct
24 Correct 6 ms 344 KB Output is correct
25 Correct 11 ms 344 KB Output is correct
26 Correct 13 ms 344 KB Output is correct
27 Correct 8 ms 344 KB Output is correct
28 Correct 10 ms 344 KB Output is correct
29 Correct 8 ms 344 KB Output is correct
30 Correct 6 ms 344 KB Output is correct
31 Correct 6 ms 344 KB Output is correct
32 Correct 6 ms 344 KB Output is correct
33 Correct 4 ms 344 KB Output is correct
34 Correct 5 ms 344 KB Output is correct
35 Correct 5 ms 344 KB Output is correct
36 Correct 6 ms 344 KB Output is correct
37 Correct 7 ms 600 KB Output is correct
38 Correct 6 ms 344 KB Output is correct
39 Correct 6 ms 344 KB Output is correct
40 Correct 7 ms 600 KB Output is correct
41 Correct 7 ms 344 KB Output is correct
42 Correct 6 ms 600 KB Output is correct
43 Correct 7 ms 344 KB Output is correct
44 Correct 8 ms 340 KB Output is correct
45 Correct 9 ms 344 KB Output is correct
46 Correct 9 ms 500 KB Output is correct
47 Correct 6 ms 344 KB Output is correct
48 Correct 12 ms 344 KB Output is correct
49 Correct 8 ms 344 KB Output is correct
50 Correct 5 ms 344 KB Output is correct
51 Correct 6 ms 440 KB Output is correct
52 Correct 7 ms 344 KB Output is correct
53 Correct 5 ms 596 KB Output is correct
54 Correct 6 ms 344 KB Output is correct
55 Correct 5 ms 344 KB Output is correct
56 Correct 4 ms 344 KB Output is correct
57 Correct 5 ms 444 KB Output is correct
58 Correct 6 ms 600 KB Output is correct
59 Correct 6 ms 440 KB Output is correct
60 Correct 6 ms 604 KB Output is correct
61 Correct 6 ms 600 KB Output is correct
62 Correct 7 ms 856 KB Output is correct
63 Correct 6 ms 600 KB Output is correct
64 Correct 6 ms 436 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 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 344 KB Output is correct
5 Correct 5 ms 600 KB Output is correct
6 Correct 8 ms 596 KB Output is correct
7 Correct 6 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 6 ms 344 KB Output is correct
10 Correct 7 ms 600 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 4 ms 344 KB Output is correct
14 Correct 11 ms 344 KB Output is correct
15 Correct 10 ms 344 KB Output is correct
16 Correct 7 ms 344 KB Output is correct
17 Correct 6 ms 344 KB Output is correct
18 Correct 6 ms 600 KB Output is correct
19 Correct 5 ms 344 KB Output is correct
20 Correct 5 ms 432 KB Output is correct
21 Correct 12 ms 340 KB Output is correct
22 Correct 11 ms 344 KB Output is correct
23 Correct 9 ms 344 KB Output is correct
24 Correct 6 ms 340 KB Output is correct
25 Correct 7 ms 344 KB Output is correct
26 Correct 5 ms 344 KB Output is correct
27 Correct 7 ms 344 KB Output is correct
28 Correct 7 ms 344 KB Output is correct
29 Correct 6 ms 344 KB Output is correct
30 Correct 6 ms 344 KB Output is correct
31 Correct 5 ms 344 KB Output is correct
32 Correct 7 ms 344 KB Output is correct
33 Correct 9 ms 344 KB Output is correct
34 Correct 8 ms 344 KB Output is correct
35 Correct 8 ms 344 KB Output is correct
36 Correct 9 ms 344 KB Output is correct
37 Correct 5 ms 344 KB Output is correct
38 Correct 8 ms 436 KB Output is correct
39 Correct 9 ms 344 KB Output is correct
40 Correct 7 ms 344 KB Output is correct
41 Correct 6 ms 344 KB Output is correct
42 Correct 7 ms 600 KB Output is correct
43 Correct 5 ms 344 KB Output is correct
44 Correct 6 ms 600 KB Output is correct
45 Correct 5 ms 344 KB Output is correct
46 Correct 5 ms 344 KB Output is correct
47 Correct 4 ms 344 KB Output is correct
48 Correct 6 ms 600 KB Output is correct
49 Correct 7 ms 600 KB Output is correct
50 Correct 7 ms 600 KB Output is correct
51 Correct 7 ms 344 KB Output is correct
52 Correct 6 ms 344 KB Output is correct
53 Correct 6 ms 432 KB Output is correct
54 Correct 6 ms 600 KB Output is correct
55 Correct 6 ms 600 KB Output is correct
56 Correct 6 ms 344 KB Output is correct
57 Correct 5 ms 432 KB Output is correct
58 Correct 7 ms 608 KB Output is correct
59 Correct 7 ms 600 KB Output is correct
60 Correct 7 ms 344 KB Output is correct
61 Correct 6 ms 344 KB Output is correct
62 Correct 5 ms 600 KB Output is correct
63 Correct 6 ms 440 KB Output is correct
64 Correct 7 ms 440 KB Output is correct
65 Correct 7 ms 600 KB Output is correct
66 Correct 6 ms 604 KB Output is correct
67 Correct 7 ms 600 KB Output is correct
68 Correct 6 ms 856 KB Output is correct
69 Correct 8 ms 856 KB Output is correct
70 Correct 6 ms 440 KB Output is correct
71 Correct 5 ms 604 KB Output is correct
72 Correct 7 ms 612 KB Output is correct
73 Correct 6 ms 444 KB Output is correct
74 Correct 6 ms 600 KB Output is correct
75 Correct 6 ms 604 KB Output is correct
76 Correct 6 ms 600 KB Output is correct
77 Correct 5 ms 604 KB Output is correct
78 Correct 6 ms 440 KB Output is correct
79 Correct 6 ms 600 KB Output is correct
80 Correct 6 ms 612 KB Output is correct
81 Correct 7 ms 440 KB Output is correct
82 Correct 7 ms 600 KB Output is correct