Submission #4234955
Source Code Expand
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string, std.datetime;
alias Point = Tuple!(long, "x", long, "y");
immutable int N = 200;
long dist2(Point p1, Point p2) {
return (p1.x - p2.x) ^^ 2 + (p1.y - p2.y) ^^ 2;
}
void main() {
auto stattime = Clock.currTime();
readln;
auto P = new Point[](N);
foreach (i; 0..N) {
auto s = readln.split.map!(to!long);
P[i] = tuple(s[0], s[1]);
}
auto D = new long[][](N, N);
long[] X;
foreach (i; 0..N) {
foreach (j; i+1..N) {
D[i][j] = D[j][i] = dist2(P[i], P[j]);
X ~= D[i][j];
}
}
X.sort();
long M = X[X.length/2];
real calc_score(const ref int[] p) {
real v = 0;
real s = 0;
foreach (i; 0..N) {
int j = (i + 1) % N;
s += D[p[i]][p[j]];
}
s /= N;
foreach (i; 0..N) {
int j = (i + 1) % N;
v += (D[p[i]][p[j]] - s) ^^ 2;
}
return v;
}
auto used = new bool[](N);
real best_score = 1L << 59;
int[] best_ans;
foreach (cur; 0..N) {
used[] = false;
int[] ans = [cur];
foreach (i; 0..N-1) {
long mind = 1L << 59;
int mini = -1;
used[cur] = true;
foreach (j; 0..N) {
if (used[j] || j == cur) continue;
long diff = abs(M - D[cur][j]);
if (diff < mind) {
mind = diff;
mini = j;
}
}
ans ~= mini;
cur = mini;
}
real s = calc_score(ans);
if (s < best_score) {
best_score = s;
best_ans = ans.dup;
}
}
while ((Clock.currTime - stattime).total!"msecs" < dur!"msecs"(1900).total!"msecs") {
int x, y;
do {
x = uniform(0, N);
y = uniform(0, N);
} while (x == y);
real old_score = best_score;
swap(best_ans[x], best_ans[y]);
real new_score = calc_score(best_ans);
if (new_score > old_score) swap(best_ans[x], best_ans[y]);
else best_score = new_score;
}
best_ans.each!writeln;
}
Submission Info
Submission Time |
|
Task |
A - Multiple Pieces |
User |
nebukuro09 |
Language |
D (LDC 0.17.0) |
Score |
0 |
Code Size |
2467 Byte |
Status |
RE |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
Score / Max Score |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
0 / 1343058 |
Status |
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
RE |
1 ms |
256 KB |
subtask_01_02.txt |
RE |
1 ms |
256 KB |
subtask_01_03.txt |
RE |
1 ms |
256 KB |
subtask_01_04.txt |
RE |
1 ms |
256 KB |
subtask_01_05.txt |
RE |
1 ms |
256 KB |
subtask_01_06.txt |
RE |
1 ms |
256 KB |
subtask_01_07.txt |
RE |
1 ms |
256 KB |
subtask_01_08.txt |
RE |
1 ms |
256 KB |
subtask_01_09.txt |
RE |
1 ms |
256 KB |
subtask_01_10.txt |
RE |
1 ms |
256 KB |