結果
| 問題 | No.3506 All Distance is Square Number |
| コンテスト | |
| ユーザー |
 gojoxd
|
| 提出日時 | 2026-04-18 19:20:40 |
| 言語 | C (gcc 15.2.0) |
| 結果 |
AC
|
| 実行時間 | 70 ms / 2,000 ms |
| コード長 | 6,208 bytes |
| 記録 | |
| コンパイル時間 | 497 ms |
| コンパイル使用メモリ | 44,392 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-04-18 19:20:57 |
| 合計ジャッジ時間 | 3,308 ms |
|
ジャッジサーバーID （参考情報） |
judge2_1 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 29 |
ソースコード
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int N;
int X[105]; // Edge weight between 1 and i
int Y[105]; // Edge weight between i and i+1
int pref[105]; // Prefix sums of Y for O(1) rim distance
bool used[205];
bool is_sq_arr[50005];
int edge_id_X[105];
int edge_id_Y[105];
void shuffle(int* array, int n) {
for (int i = 0; i < n; i++) {
int j = i + rand() % (n - i);
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}
// O(1) calculation of distance on the rim
int rim_dist(int a, int b) {
return abs(pref[a] - pref[b]);
}
// O(N^2) maximum check, extremely fast with intervals
bool has_square_path(int j, int i, int n) {
if (j == 1) {
for (int y = 2; y <= n; y++) {
if (is_sq_arr[X[y] + rim_dist(y, i)]) return true;
}
return false;
}
if (is_sq_arr[rim_dist(j, i)]) return true; // Pure rim path
for (int x = 2; x <= n; x++) {
for (int y = 2; y <= n; y++) {
if (x == y) continue;
// Intervals must be strictly disjoint for a simple path
int min_jx = MIN(j, x), max_jx = MAX(j, x);
int min_iy = MIN(i, y), max_iy = MAX(i, y);
if (max_jx < min_iy || max_iy < min_jx) {
int sum = rim_dist(j, x) + X[x] + X[y] + rim_dist(y, i);
if (is_sq_arr[sum]) return true;
}
}
}
return false;
}
// Backtracking to assign distinct weights deterministically
bool solve(int step) {
if (step > N) return true;
int candidates_X[205], cx = 0;
for (int w = 1; w <= 200; w++) if (!used[w]) candidates_X[cx++] = w;
shuffle(candidates_X, cx);
if (step == 2) {
for (int i = 0; i < cx; i++) {
int x_val = candidates_X[i];
if (!is_sq_arr[x_val]) continue; // Direct edge 1-2 MUST be a square
used[x_val] = true;
X[2] = x_val;
if (solve(3)) return true;
used[x_val] = false;
}
return false;
}
int candidates_Y[205], cy = 0;
for (int w = 1; w <= 200; w++) if (!used[w]) candidates_Y[cy++] = w;
shuffle(candidates_Y, cy);
for (int ix = 0; ix < cx; ix++) {
int x_val = candidates_X[ix];
used[x_val] = true;
X[step] = x_val;
for (int iy = 0; iy < cy; iy++) {
int y_val = candidates_Y[iy];
if (y_val == x_val || used[y_val]) continue;
used[y_val] = true;
Y[step - 1] = y_val;
pref[step] = pref[step - 1] + y_val; // Update O(1) prefix sum
bool ok = true;
for (int j = step - 1; j >= 1; j--) {
if (!has_square_path(j, step, step)) {
ok = false;
break;
}
}
if (ok && solve(step + 1)) return true;
used[y_val] = false;
}
used[x_val] = false;
}
return false;
}
void print_square_path(int j, int i, int n) {
if (j == 1) {
for (int y = 2; y <= n; y++) {
if (is_sq_arr[X[y] + rim_dist(y, i)]) {
int len = 1 + abs(i - y);
printf("%d %d", len, edge_id_X[y]);
int curr = y, step = (i > y) ? 1 : -1;
while (curr != i) {
int next = curr + step;
printf(" %d", edge_id_Y[MIN(curr, next)]);
curr = next;
}
printf("\n");
return;
}
}
} else {
if (is_sq_arr[rim_dist(j, i)]) {
int len = abs(i - j);
printf("%d", len);
int curr = j, step = (i > j) ? 1 : -1;
while (curr != i) {
int next = curr + step;
printf(" %d", edge_id_Y[MIN(curr, next)]);
curr = next;
}
printf("\n");
return;
}
for (int x = 2; x <= n; x++) {
for (int y = 2; y <= n; y++) {
if (x == y) continue;
int min_jx = MIN(j, x), max_jx = MAX(j, x);
int min_iy = MIN(i, y), max_iy = MAX(i, y);
if (max_jx < min_iy || max_iy < min_jx) {
if (is_sq_arr[rim_dist(j, x) + X[x] + X[y] + rim_dist(y, i)]) {
int len = abs(x - j) + 2 + abs(i - y);
printf("%d", len);
int curr = j, step = (x > j) ? 1 : -1;
while (curr != x) {
int next = curr + step;
printf(" %d", edge_id_Y[MIN(curr, next)]);
curr = next;
}
printf(" %d %d", edge_id_X[x], edge_id_X[y]);
curr = y; step = (i > y) ? 1 : -1;
while (curr != i) {
int next = curr + step;
printf(" %d", edge_id_Y[MIN(curr, next)]);
curr = next;
}
printf("\n");
return;
}
}
}
}
}
}
int main() {
if (scanf("%d", &N) != 1) return 0;
// Precompute perfect squares up to max possible sum
for (int i = 0; i <= 223; i++) {
if (i * i <= 50000) is_sq_arr[i * i] = true;
}
srand(1337);
pref[2] = 0;
solve(2);
int M = 0;
printf("%d\n", (N > 2) ? 2 * N - 3 : 1);
for (int i = 2; i <= N; i++) {
M++;
edge_id_X[i] = M;
printf("1 %d %d\n", i, X[i]);
}
for (int i = 2; i <= N - 1; i++) {
M++;
edge_id_Y[i] = M;
printf("%d %d %d\n", i, i + 1, Y[i]);
}
// Output valid paths immediately
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
print_square_path(i, j, N);
}
}
return 0;
}