답안 #841857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841857	2023-09-02T07:41:46 Z	anhduc2701	가장 긴 여행 (IOI23_longesttrip)	C++17	100 / 100	15 ms	856 KB

longesttrip

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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