winner_ups_global

#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <algorithm>
#include <cmath>
#include <unordered_set>
#include <random>
#include <sstream>
#include <string>
#include <iomanip>
using namespace std;

const double p=0.0174532925199432957692369076848861271344287188854172545609719;
const double r=6371;

inline double dist(const pair<double, double>&, const pair<double, double>&);
double score(vector<int>);
void init(void);
void out(vector<int>);
vector<int> in(string);
void tryperm(vector<int>&,int);
void trypermr(vector<int>&,int,int);
void tryswap1(vector<int>&,int);
void tryswap2(vector<int>&,int);

//

#define MAXN 400
ifstream fin("cities.txt");
int N;
double d[MAXN][MAXN];

vector<int> NN(int i){
	unordered_set<int> a;
	vector<int> ans;
	ans.push_back(i);
	a.insert(i);
	for(int i=1;i<N;i++){
		double best=INFINITY;
		int id;
		for(int j=0;j<N;j++){
			if(!a.count(j)){
				if(d[ans.back()][j]<best){
					best=d[ans.back()][j];
					id=j;
				}
			}
		}
		ans.push_back(id);
		a.insert(id);
	}

	return ans;
}

mt19937 rng;

int main(){
	rng.seed(time(NULL));
	ios_base::sync_with_stdio(0);
	init();

	vector<int> list=in("239318.txt");

	tryswap1(list,1000);
	tryswap2(list,100000);
	tryperm(list,8);
	trypermr(list,12,1000000);
	while(true){
		tryswap1(list,10000);
		tryswap2(list,10000);
		trypermr(list,10,10000);
		trypermr(list,50,10000);
	}

	return 0;
}

//

void tryswap1(vector<int>& list,int count){
	uniform_int_distribution<int> pos1(0,N-2);
	double best=score(list);
	for(int i=0;i<count;i++){
		int k=pos1(rng);
		swap(list[k],list[k+1]);
		if(score(list)>best){
			swap(list[k],list[k+1]);
		} else {
			best=score(list);
			out(list);
		}
	}
	return;
}

void tryswap2(vector<int>& list,int count){
	uniform_int_distribution<int> pos(0,N-1);
	double best=score(list);
	for(int i=0;i<count;i++){
		int x=pos(rng);
		int y=pos(rng);
		swap(list[x],list[y]);
		if(score(list)>best){
			swap(list[x],list[y]);
		} else {
			best=score(list);
			out(list);
		}
	}
	return;
}

void trypermr(vector<int>& list,int blocks,int count){
	vector<pair<double, int> > za;
	for(int i=0;i+1<N;i++){
		za.push_back(make_pair(-d[list[i]][list[i+1]],i));
	}
	unordered_set<int> va;
	sort(za.begin(), za.end());
	for(int i=0;i<blocks;i++)
		va.insert(za[i].second);
	vector<vector<int> > ba;
	vector<int> cur;
	for(int i=0;i<N;i++){
		cur.push_back(list[i]);
		if(va.count(i)){
			ba.push_back(cur);
			cur.resize(0);
		}
	}
	ba.push_back(cur);
	vector<int> per(blocks+1);
	for(int i=0;i<blocks+1;i++)
		per[i]=i;

	double best=score(list);

	for(int T=0;T<count;T++){
		random_shuffle(per.begin(), per.end());
		vector<int> ne;
		for(const auto& v:per)
			for(const auto& i:ba[v])
				ne.push_back(i);
		if(score(ne)<best){
			list=ne;
			best=score(ne);
			out(list);
		}
	}
	return;
}

void tryperm(vector<int>& list,int blocks){
	vector<pair<double, int> > za;
	for(int i=0;i+1<N;i++){
		za.push_back(make_pair(-d[list[i]][list[i+1]],i));
	}
	unordered_set<int> va;
	sort(za.begin(), za.end());
	for(int i=0;i<blocks;i++)
		va.insert(za[i].second);
	vector<vector<int> > ba;
	vector<int> cur;
	for(int i=0;i<N;i++){
		cur.push_back(list[i]);
		if(va.count(i)){
			ba.push_back(cur);
			cur.resize(0);
		}
	}
	ba.push_back(cur);
	vector<int> per(blocks+1);
	for(int i=0;i<blocks+1;i++)
		per[i]=i;

	double best=score(list);

	do{
		vector<int> ne;
		for(const auto& v:per)
			for(const auto& i:ba[v])
				ne.push_back(i);
		if(score(ne)<best){
			list=ne;
			best=score(ne);
			out(list);
		}
	}while(next_permutation(per.begin(),per.end()));
	return;
}

vector<int> in(string s){
	ifstream fi(s);
	vector<int> a(N);
	for(auto& b:a)
		fi>>b;
	return a;
}

void out(vector<int> list){
	stringstream ss;
	ss << (int)score(list) << ".txt";
	cout << "OUTPUTTING " << ss.str() << endl;
	ofstream fout(ss.str());
	fout << fixed << setprecision(10);
	for(const auto& c: list)
		fout << c << endl;
	return;
}

double score(vector<int> list){
	if((int)list.size()!=N) return INFINITY;
	vector<int> a(list);
	sort(a.begin(),a.end());
	for(int i=0;i<N;i++)
		if(a[i]!=i)
			return INFINITY;
	double sc=0;
	for(int i=1;i<N;i++)
		sc+=d[list[i]][list[i-1]];
	sc+=d[list[N-1]][list[0]];
	return sc;
}

double dist(const pair<double, double>& a, const pair<double, double>& b){
	return r*acos(sin(a.first)*sin(b.first)+cos(a.first)*cos(b.first)*cos(b.second-a.second));
}

void init(void){
	fin >> N;

	vector<pair<double, double> > c;
	for(int i=0;i<N;i++){
		int a,b; char s;
		fin >> a >> b >> s;
		double lat=p*(s=='N'?1:-1)*(a+b/60.0);
		fin >> a >> b >> s;
		double lon=p*(s=='E'?1:-1)*(a+b/60.0);
		c.push_back(make_pair(lat,lon));
	}

	for(int i=0;i<N;i++)
		for(int j=i+1;j<N;j++)
			d[i][j]=d[j][i]=dist(c[i],c[j]);
	for(int i=0;i<N;i++)
		d[i][i]=0;

	return;
}

/*
cities.txt:
339
34 20 N 62 12 E
34 31 N 69 12 E
36 50 N 3 00 E
14 16 S 170 43 W
42 30 N 1 30 E
15 10 S 12 09 E
18 13 N 63 03 W
34 40 S 58 30 W
31 32 S 64 21 W
40 10 N 44 31 E
12 31 N 70 02 W
34 55 S 138 35 E
23 42 S 133 53 E
27 28 S 153 02 E
35 17 S 149 08 E
28 56 S 134 45 E
12 28 S 130 50 E
17 19 S 123 38 E
23 20 S 119 34 E
31 56 S 115 50 E
19 13 S 146 48 E
48 12 N 16 22 E
40 22 N 49 53 E
25 03 N 77 29 W
26 13 N 50 34 E
23 43 N 90 25 E
13 06 N 59 37 W
53 51 N 27 30 E
50 50 N 4 20 E
17 13 N 88 48 W
6 29 N 2 37 E
32 18 N 64 48 W
27 32 N 89 43 E
16 30 S 68 10 W
43 51 N 18 23 E
24 45 S 25 55 E
1 27 S 48 29 W
15 47 S 47 55 W
22 54 S 47 03 W
7 15 S 58 25 W
3 06 S 60 00 W
8 45 S 63 54 W
8 06 S 34 53 W
22 54 S 43 14 W
2 26 S 54 41 W
23 32 S 46 37 W
18 28 N 64 39 W
4 53 N 114 56 E
42 40 N 23 18 E
12 22 N 1 31 W
3 22 S 29 19 E
11 33 N 104 55 E
3 51 N 11 35 E
58 45 N 94 00 W
67 49 N 115 21 W
45 25 N 75 43 W
56 15 N 117 18 W
46 50 N 71 15 W
52 10 N 101 32 W
43 39 N 79 23 W
49 16 N 123 07 W
60 43 N 135 03 W
49 53 N 97 09 W
14 55 N 23 31 W
19 20 N 81 23 W
4 23 N 18 37 E
12 10 N 14 59 E
23 40 S 70 23 W
27 05 S 109 20 W
33 27 S 70 40 W
54 55 S 67 37 W
53 10 S 70 56 W
39 40 S 73 13 W
39 55 N 116 26 E
45 45 N 126 41 E
25 04 N 102 41 E
31 06 N 121 22 E
43 43 N 87 38 E
30 35 N 108 54 E
25 05 N 121 32 E
12 10 S 96 49 E
4 36 N 74 05 W
11 40 S 43 16 E
4 46 S 11 53 E
4 18 S 15 18 E
0 33 N 25 14 E
11 41 S 27 29 E
21 12 S 159 46 E
9 56 N 84 05 W
5 19 N 0 05 W
6 49 N 5 17 W
45 48 N 15 58 E
12 12 N 68 56 W
35 10 N 33 22 E
49 13 N 16 40 E
50 06 N 14 26 E
4 18 S 15 18 E
55 45 N 12 25 E
11 33 N 43 10 E
15 18 N 61 23 W
18 28 N 69 54 W
2 10 S 79 50 W
0 14 S 78 30 W
24 05 N 32 56 E
30 03 N 31 15 E
13 40 N 89 10 W
52 28 N 01 54 W
51 28 N 00 00 W
51 30 N 0 10 W
3 45 N 8 48 E
15 20 N 38 58 E
59 26 N 24 43 E
9 03 N 38 42 E
51 45 S 57 56 W
62 01 N 6 46 W
17 47 S 177 29 E
18 08 S 178 25 E
60 08 N 25 00 E
44 50 N 0 34 W
43 42 N 7 15 E
48 52 N 2 20 E
4 00 N 52 30 W
23 10 S 135 00 W
17 32 S 149 34 W
0 30 N 9 25 E
13 28 N 16 39 W
41 43 N 44 49 E
52 32 N 13 25 E
53 33 N 9 59 E
5 33 N 0 15 W
36 09 N 5 21 W
37 58 N 23 43 E
64 10 N 51 35 W
77 42 N 68 30 W
12 04 N 61 44 E
16 10 N 61 40 W
13 28 N 144 45 E
14 38 N 90 31 W
49 27 N 2 32 W
9 29 N 13 43 W
11 52 N 15 39 W
6 48 N 58 10 W
18 32 N 72 20 W
14 05 N 87 14 W
22 15 N 114 10 E
47 30 N 19 05 E
64 09 N 21 51 W
12 58 N 77 35 E
22 30 N 88 20 E
28 40 N 77 14 E
23 03 N 70 11 E
18 56 N 74 35 E
21 10 N 79 12 E
6 08 S 106 45 E
33 20 N 44 26 E
51 54 N 8 28 W
53 20 N 6 15 W
54 09 N 4 29 W
31 47 N 35 13 E
32 5 N 34 48 E
43 46 N 11 15 E
40 51 N 14 17 E
41 48 N 12 36 E
17 58 N 76 48 W
34 23 N 132 27 E
31 37 N 130 32 E
34 41 N 135 12 E
35 1 N 135 46 E
32 47 N 129 52 E
26 12 N 127 41 E
34 42 N 135 30 E
43 05 N 141 21 E
35 40 N 139 45 E
49 11 N 2 07 W
31 57 N 35 56 E
51 10 N 71 30 E
54 53 N 69 13 E
1 17 S 36 49 E
1 30 N 173 00 E
37 30 N 127 00 E
29 20 N 48 00 E
42 53 N 74 46 E
17 58 N 102 36 E
33 52 N 35 30 E
29 19 S 27 29 E
6 18 N 10 47 W
47 08 N 9 32 E
54 41 N 25 19 E
49 37 N 6 08 E
56 40 N 106 10 E
32 07 N 20 04 E
32 54 N 13 11 E
18 52 S 47 30 E
13 58 S 33 49 E
05 25 N 100 19 E
1 29 N 103 44 E
6 8 N 102 15 E
2 33 N 102 10 E
1 33 N 110 25 E
3 08 N 101 42 E
4 00 N 73 28 E
12 39 N 8 00 W
16 49 N 2 59 W
35 54 N 14 32 E
34 02 N 6 51 W
7 05 N 171 08 E
14 36 N 61 05 W
18 09 N 15 58 W
20 10 S 57 30 E
12 47 S 45 14 E
28 40 N 106 06 W
20 40 N 103 20 W
19 24 N 99 09 W
32 32 N 117 01 W
19 12 N 96 08 W
6 58 N 158 13 E
47 00 N 28 50 E
43 45 N 7 23 E
47 54 N 106 52 E
42 28 N 19 17 E
16 44 N 62 14 W
29 24 N 10 12 W
19 49 S 34 52 E
25 58 S 32 35 E
26 38 S 15 10 E
22 34 S 17 06 E
27 42 N 85 19 E
52 21 N 4 54 E
22 16 S 166 26 E
36 55 S 174 47 E
44 23 S 171 14 E
41 17 S 174 47 E
12 06 N 86 18 W
13 32 N 2 05 E
9 10 N 7 11 E
12 00 N 8 31 E
6 27 N 3 24 E
19 01 S 169 55 E
29 04 S 167 57 E
78 12 N 15 40 E
59 55 N 10 45 E
23 37 N 58 38 E
17 00 N 54 04 E
33 40 N 73 08 E
24 51 N 67 02 E
7 21 N 134 31 E
8 58 N 79 32 W
9 30 S 147 07 E
25 16 S 57 40 W
16 25 S 71 32 W
3 51 S 73 13 W
12 03 S 77 03 W
14 35 N 120 59 E
25 04 S 130 05 W
52 15 N 21 00 E
54 23 N 18 40 E
38 44 N 9 08 W
18 28 N 66 07 W
25 15 N 51 36 E
4 14 N 15 14 E
42 00 N 21 28 E
20 52 S 55 27 E
44 26 N 26 06 E
52 03 N 113 35 E
45 02 N 39 00 E
55 45 N 37 42 E
54 59 N 73 22 E
59 56 N 30 20 E
43 09 N 131 53 E
1 56 S 30 04 E
46 46 N 56 11 W
15 56 S 5 44 W
17 18 N 62 43 W
14 01 N 60 59 W
13 12 N 61 14 W
13 48 S 171 45 W
43 56 N 12 26 E
0 19 N 6 43 E
24 39 N 46 46 E
55 53 N 4 15 W
14 40 N 17 26 W
44 50 N 20 30 E
4 38 S 55 28 E
8 30 N 13 15 W
1 18 N 103 50 E
48 10 N 17 10 E
46 04 N 14 30 E
9 28 S 159 57 E
2 02 N 45 21 E
35 55 S 18 22 E
26 08 S 27 54 E
33 58 S 25 36 E
25 45 S 28 12 E
37 32 N 127 00 E
41 23 N 2 11 E
40 24 N 3 41 W
6 55 N 79 52 E
5 50 N 55 10 W
26 20 S 31 08 E
59 20 N 18 03 E
46 57 N 7 27 E
47 22 N 8 33 E
38 38 N 68 51 E
6 51 S 39 18 E
10 00 S 39 41 E
6 10 S 39 20 E
13 44 N 100 30 E
6 08 N 1 13 E
21 09 S 175 14 W
10 38 N 61 31 W
36 48 N 10 11 E
34 44 N 10 46 E
39 55 N 32 50 E
41 01 N 28 58 E
41 00 N 39 43 E
37 58 N 58 24 E
8 31 S 179 13 E
18 22 N 64 56 W
0 19 N 35 25 E
50 25 N 30 43 E
24 28 N 54 22 E
25 16 N 55 20 E
41 53 N 87 39 W
21 18 N 157 49 W
29 45 N 95 22 W
34 03 N 118 15 W
40 43 N 74 00 W
34 53 S 56 11 W
41 16 N 69 13 E
17 45 S 168 18 E
10 30 N 66 56 W
8 24 N 71 08 W
21 01 N 105 52 E
10 46 N 106 43 E
13 22 S 176 12 W
15 24 N 44 14 E
15 26 S 28 20 E
1 04 N 34 12 E
17 50 S 31 30 E
*/