Skip to content

Instantly share code, notes, and snippets.

@siman-man

siman-man/SurfaceReconstruction.cpp Secret

Created July 31, 2023 09:04
Show Gist options
  • Save siman-man/2218aee9a4a99e3bc6c780dbb72066ba to your computer and use it in GitHub Desktop.
Save siman-man/2218aee9a4a99e3bc6c780dbb72066ba to your computer and use it in GitHub Desktop.
Download ZIP
MM147
Raw
SurfaceReconstruction.cpp
#include <cassert>
#include <cmath>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <climits>
#include <map>
#include <queue>
#include <set>
#include <cstring>
#include <vector>
using namespace std;
using namespace std::chrono;
typedef long long ll;
typedef pair<double, double> P;
const ll CYCLE_PER_SEC = 2700000000;
double TIME_LIMIT = 5.0;
unsigned long long xor128() {
static unsigned long long rx = 123456789, ry = 362436069, rz = 521288629, rw = 88675123;
unsigned long long rt = (rx ^ (rx << 11));
rx = ry;
ry = rz;
rz = rw;
return (rw = (rw ^ (rw >> 19)) ^ (rt ^ (rt >> 8)));
}
unsigned long long int get_cycle() {
unsigned int low, high;
__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
return ((unsigned long long int) low) | ((unsigned long long int) high << 32);
}
double get_time(high_resolution_clock::time_point &begin) {
high_resolution_clock::time_point end = high_resolution_clock::now();
ll count = duration_cast<microseconds>(end - begin).count();
return count / 1000000.0;
}
double get_time(unsigned long long int begin_cycle) {
return (double) (get_cycle() - begin_cycle) / CYCLE_PER_SEC;
}
// 高速なexpの近似値を求める関数
double fast_exp(double x) {
// 事前計算したテーブルのサイズと範囲
const int table_size = 8192;
const double table_min = -20.0;
const double table_max = 20.0;
// 事前計算したexpの近似値テーブル
static double exp_table[table_size];
// テーブルが初期化されていなければ初期化
static bool is_table_initialized = false;
if (!is_table_initialized) {
for (int i = 0; i < table_size; i++) {
double t = i * (table_max - table_min) / table_size + table_min;
exp_table[i] = std::exp(t);
}
is_table_initialized = true;
}
// xがテーブルの範囲外の場合、近似値を補間して求める
if (x <= table_min) return exp_table[0];
if (x >= table_max) return exp_table[table_size - 1];
// 近似値を補間して求める
double t = (x - table_min) * table_size / (table_max - table_min);
int idx1 = static_cast<int>(t);
int idx2 = idx1 + 1;
double frac = t - idx1;
return (1.0 - frac) * exp_table[idx1] + frac * exp_table[idx2];
}
int N;
double A;
const int MAX_N = 60;
const int GRID_SIZE = MAX_N + 2;
const int MAX_E = 50;
const int SLOPE = 0;
const int SINCOS = 1;
const int XOR = 2;
const int XY2 = 3;
const int DZ[8] = {-GRID_SIZE, 1, GRID_SIZE, -1, -GRID_SIZE - 1, -GRID_SIZE + 1, GRID_SIZE - 1, GRID_SIZE + 1};
int g_surface[GRID_SIZE * GRID_SIZE];
int g_correct_surface[GRID_SIZE * GRID_SIZE];
double g_grid[GRID_SIZE * GRID_SIZE];
bool g_is_checked[GRID_SIZE * GRID_SIZE];
bool g_is_wall[GRID_SIZE * GRID_SIZE];
vector<int> g_checked_positions;
ll g_visited[GRID_SIZE * GRID_SIZE];
ll g_vid;
double g_exp_mse[61][81] = {
{INT_MAX, 37398, 19532, 10285, 5500, 3024, 1743, 1079, 736, 559, 467, 419, 394, 382, 375, 372, 370, 369, 369, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368, 368},
{INT_MAX, 34086, 19738, 11520, 6814, 4119, 2576, 1692, 1185, 895, 729, 634, 580, 549, 531, 521, 515, 511, 509, 508, 508, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507, 507},
{INT_MAX, 30256, 18894, 11895, 7583, 4927, 3290, 2282, 1661, 1278, 1043, 897, 808, 753, 719, 698, 685, 677, 672, 669, 667, 666, 666, 665, 665, 665, 665, 665, 665, 665, 665, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664, 664},
{INT_MAX, 34809, 20651, 12345, 7472, 4612, 2935, 1951, 1373, 1034, 835, 719, 650, 610, 587, 573, 565, 560, 557, 556, 555, 554, 554, 554, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553, 553},
{INT_MAX, 38236, 23594, 14647, 9179, 5838, 3796, 2548, 1785, 1319, 1034, 860, 754, 689, 649, 625, 610, 601, 596, 592, 590, 589, 588, 588, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587, 587},
{INT_MAX, 23177, 16990, 12476, 9181, 6776, 5021, 3741, 2806, 2124, 1627, 1264, 998, 805, 664, 561, 486, 431, 391, 362, 340, 325, 313, 305, 299, 295, 291, 289, 287, 286, 285, 284, 284, 284, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283, 283},
{INT_MAX, 29903, 20822, 14548, 10215, 7221, 5154, 3725, 2738, 2057, 1586, 1261, 1036, 881, 773, 699, 648, 613, 588, 572, 560, 552, 546, 542, 540, 538, 537, 536, 535, 535, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534, 534},
{INT_MAX, 25031, 18195, 13267, 9713, 7152, 5305, 3973, 3013, 2321, 1822, 1462, 1202, 1015, 881, 783, 713, 663, 626, 600, 581, 567, 558, 551, 545, 542, 539, 537, 536, 535, 534, 534, 533, 533, 533, 533, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532, 532},
{INT_MAX, 25464, 18758, 13860, 10281, 7666, 5756, 4361, 3342, 2597, 2053, 1655, 1365, 1153, 998, 885, 802, 742, 697, 665, 642, 624, 612, 603, 596, 591, 587, 585, 583, 581, 580, 580, 579, 579, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578, 578},
{INT_MAX, 35851, 25208, 17793, 12626, 9025, 6517, 4769, 3551, 2702, 2111, 1699, 1412, 1212, 1073, 976, 908, 861, 828, 805, 789, 778, 770, 765, 761, 758, 757, 755, 754, 754, 753, 753, 753, 753, 753, 753, 753, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752, 752},
{INT_MAX, 25770, 19767, 15187, 11693, 9028, 6995, 5444, 4261, 3358, 2670, 2145, 1744, 1438, 1205, 1027, 892, 788, 709, 649, 603, 568, 541, 521, 505, 493, 484, 477, 472, 468, 465, 463, 461, 460, 459, 458, 457, 457, 456, 456, 456, 456, 456, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455, 455},
{INT_MAX, 36667, 26620, 19402, 14216, 10491, 7815, 5892, 4511, 3518, 2805, 2293, 1925, 1661, 1471, 1335, 1237, 1166, 1116, 1079, 1053, 1034, 1021, 1011, 1004, 999, 996, 993, 991, 990, 989, 988, 988, 988, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987, 987},
{INT_MAX, 37095, 26795, 19436, 14178, 10422, 7738, 5821, 4451, 3473, 2774, 2274, 1917, 1662, 1480, 1350, 1257, 1191, 1143, 1110, 1085, 1068, 1056, 1047, 1040, 1036, 1033, 1030, 1029, 1028, 1027, 1026, 1026, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025, 1025},
{INT_MAX, 32946, 24675, 18546, 14003, 10637, 8142, 6294, 4923, 3908, 3155, 2598, 2185, 1878, 1651, 1483, 1358, 1266, 1198, 1147, 1109, 1081, 1061, 1045, 1034, 1026, 1019, 1015, 1011, 1009, 1007, 1006, 1005, 1004, 1003, 1003, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002, 1002},
{INT_MAX, 40077, 29047, 21139, 15469, 11404, 8489, 6400, 4901, 3827, 3057, 2504, 2108, 1825, 1621, 1475, 1370, 1295, 1242, 1203, 1175, 1156, 1141, 1131, 1124, 1119, 1115, 1112, 1110, 1109, 1108, 1107, 1107, 1106, 1106, 1106, 1106, 1106, 1106, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105, 1105},
{INT_MAX, 38904, 28752, 21295, 15818, 11796, 8841, 6671, 5077, 3907, 3047, 2415, 1952, 1611, 1361, 1177, 1042, 943, 870, 817, 777, 748, 727, 712, 700, 692, 686, 681, 678, 675, 674, 672, 671, 671, 670, 670, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669, 669},
{INT_MAX, 45039, 32942, 24175, 17822, 13217, 9881, 7462, 5710, 4440, 3519, 2852, 2369, 2018, 1764, 1580, 1447, 1350, 1280, 1230, 1193, 1166, 1147, 1133, 1123, 1115, 1110, 1106, 1103, 1101, 1100, 1099, 1098, 1098, 1097, 1097, 1097, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096, 1096},
{INT_MAX, 37051, 28261, 21612, 16583, 12778, 9900, 7724, 6077, 4832, 3889, 3177, 2638, 2230, 1921, 1688, 1512, 1378, 1277, 1201, 1143, 1099, 1066, 1041, 1022, 1008, 997, 989, 983, 978, 975, 972, 970, 968, 967, 966, 966, 965, 965, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964},
{INT_MAX, 37051, 28261, 21612, 16583, 12778, 9900, 7724, 6077, 4832, 3889, 3177, 2638, 2230, 1921, 1688, 1512, 1378, 1277, 1201, 1143, 1099, 1066, 1041, 1022, 1008, 997, 989, 983, 978, 975, 972, 970, 968, 967, 966, 966, 965, 965, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964, 964},
{INT_MAX, 36322, 28573, 22507, 17757, 14038, 11126, 8846, 7061, 5663, 4569, 3712, 3041, 2516, 2104, 1782, 1530, 1333, 1178, 1057, 963, 888, 830, 785, 749, 721, 699, 682, 669, 658, 650, 644, 639, 635, 632, 629, 627, 626, 625, 624, 623, 623, 622, 622, 622, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621},
{INT_MAX, 36322, 28573, 22507, 17757, 14038, 11126, 8846, 7061, 5663, 4569, 3712, 3041, 2516, 2104, 1782, 1530, 1333, 1178, 1057, 963, 888, 830, 785, 749, 721, 699, 682, 669, 658, 650, 644, 639, 635, 632, 629, 627, 626, 625, 624, 623, 623, 622, 622, 622, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621},
{INT_MAX, 36322, 28573, 22507, 17757, 14038, 11126, 8846, 7061, 5663, 4569, 3712, 3041, 2516, 2104, 1782, 1530, 1333, 1178, 1057, 963, 888, 830, 785, 749, 721, 699, 682, 669, 658, 650, 644, 639, 635, 632, 629, 627, 626, 625, 624, 623, 623, 622, 622, 622, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621, 621},
{INT_MAX, 59858, 42899, 30885, 22375, 16346, 12075, 9049, 6906, 5387, 4312, 3550, 3010, 2627, 2357, 2165, 2029, 1932, 1864, 1816, 1782, 1757, 1740, 1728, 1719, 1713, 1709, 1706, 1704, 1702, 1701, 1700, 1700, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698},
{INT_MAX, 59858, 42899, 30885, 22375, 16346, 12075, 9049, 6906, 5387, 4312, 3550, 3010, 2627, 2357, 2165, 2029, 1932, 1864, 1816, 1782, 1757, 1740, 1728, 1719, 1713, 1709, 1706, 1704, 1702, 1701, 1700, 1700, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1699, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698, 1698},
{INT_MAX, 34159, 27618, 22364, 18145, 14756, 12034, 9848, 8092, 6682, 5549, 4639, 3909, 3322, 2850, 2472, 2168, 1924, 1728, 1570, 1444, 1342, 1260, 1195, 1142, 1100, 1066, 1039, 1017, 999, 985, 974, 965, 957, 951, 947, 943, 940, 937, 935, 934, 932, 931, 931, 930, 929, 929, 929, 928, 928, 928, 928, 928, 928, 928, 928, 928, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927},
{INT_MAX, 34159, 27618, 22364, 18145, 14756, 12034, 9848, 8092, 6682, 5549, 4639, 3909, 3322, 2850, 2472, 2168, 1924, 1728, 1570, 1444, 1342, 1260, 1195, 1142, 1100, 1066, 1039, 1017, 999, 985, 974, 965, 957, 951, 947, 943, 940, 937, 935, 934, 932, 931, 931, 930, 929, 929, 929, 928, 928, 928, 928, 928, 928, 928, 928, 928, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927},
{INT_MAX, 34159, 27618, 22364, 18145, 14756, 12034, 9848, 8092, 6682, 5549, 4639, 3909, 3322, 2850, 2472, 2168, 1924, 1728, 1570, 1444, 1342, 1260, 1195, 1142, 1100, 1066, 1039, 1017, 999, 985, 974, 965, 957, 951, 947, 943, 940, 937, 935, 934, 932, 931, 931, 930, 929, 929, 929, 928, 928, 928, 928, 928, 928, 928, 928, 928, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927, 927},
{INT_MAX, 41243, 32460, 25609, 20267, 16101, 12851, 10317, 8341, 6800, 5598, 4661, 3930, 3359, 2915, 2568, 2298, 2087, 1922, 1794, 1694, 1616, 1555, 1508, 1471, 1442, 1419, 1402, 1388, 1377, 1369, 1363, 1357, 1354, 1350, 1348, 1346, 1345, 1344, 1343, 1342, 1341, 1341, 1341, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340},
{INT_MAX, 41243, 32460, 25609, 20267, 16101, 12851, 10317, 8341, 6800, 5598, 4661, 3930, 3359, 2915, 2568, 2298, 2087, 1922, 1794, 1694, 1616, 1555, 1508, 1471, 1442, 1419, 1402, 1388, 1377, 1369, 1363, 1357, 1354, 1350, 1348, 1346, 1345, 1344, 1343, 1342, 1341, 1341, 1341, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340, 1340},
{INT_MAX, 25092, 21740, 18849, 16356, 14207, 12353, 10755, 9376, 8188, 7163, 6279, 5517, 4859, 4292, 3804, 3382, 3019, 2705, 2435, 2202, 2001, 1828, 1678, 1549, 1438, 1342, 1260, 1189, 1127, 1074, 1028, 989, 955, 926, 900, 879, 860, 844, 830, 818, 807, 798, 791, 784, 778, 773, 769, 765, 762, 759, 757, 755, 753, 752, 750, 749, 748, 747, 747, 746, 746, 745, 745, 744, 744, 744, 744, 743, 743, 743, 743, 743, 743, 743, 743, 743, 743, 742, 742, 742},
{INT_MAX, 25092, 21740, 18849, 16356, 14207, 12353, 10755, 9376, 8188, 7163, 6279, 5517, 4859, 4292, 3804, 3382, 3019, 2705, 2435, 2202, 2001, 1828, 1678, 1549, 1438, 1342, 1260, 1189, 1127, 1074, 1028, 989, 955, 926, 900, 879, 860, 844, 830, 818, 807, 798, 791, 784, 778, 773, 769, 765, 762, 759, 757, 755, 753, 752, 750, 749, 748, 747, 747, 746, 746, 745, 745, 744, 744, 744, 744, 743, 743, 743, 743, 743, 743, 743, 743, 743, 743, 742, 742, 742},
{INT_MAX, 25092, 21740, 18849, 16356, 14207, 12353, 10755, 9376, 8188, 7163, 6279, 5517, 4859, 4292, 3804, 3382, 3019, 2705, 2435, 2202, 2001, 1828, 1678, 1549, 1438, 1342, 1260, 1189, 1127, 1074, 1028, 989, 955, 926, 900, 879, 860, 844, 830, 818, 807, 798, 791, 784, 778, 773, 769, 765, 762, 759, 757, 755, 753, 752, 750, 749, 748, 747, 747, 746, 746, 745, 745, 744, 744, 744, 744, 743, 743, 743, 743, 743, 743, 743, 743, 743, 743, 742, 742, 742},
{INT_MAX, 50821, 39557, 30889, 24220, 19088, 15139, 12101, 9763, 7964, 6580, 5515, 4696, 4065, 3580, 3207, 2919, 2698, 2528, 2397, 2297, 2219, 2159, 2114, 2078, 2051, 2030, 2014, 2002, 1992, 1985, 1979, 1975, 1972, 1969, 1967, 1966, 1964, 1963, 1963, 1962, 1962, 1962, 1961, 1961, 1961, 1961, 1961, 1961, 1961, 1961, 1961, 1961, 1961, 1961, 1961, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960},
{INT_MAX, 50821, 39557, 30889, 24220, 19088, 15139, 12101, 9763, 7964, 6580, 5515, 4696, 4065, 3580, 3207, 2919, 2698, 2528, 2397, 2297, 2219, 2159, 2114, 2078, 2051, 2030, 2014, 2002, 1992, 1985, 1979, 1975, 1972, 1969, 1967, 1966, 1964, 1963, 1963, 1962, 1962, 1962, 1961, 1961, 1961, 1961, 1961, 1961, 1961, 1961, 1961, 1961, 1961, 1961, 1961, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960, 1960},
{INT_MAX, 38294, 31931, 26660, 22292, 18673, 15675, 13190, 11132, 9427, 8014, 6843, 5873, 5070, 4404, 3852, 3395, 3016, 2703, 2443, 2227, 2049, 1901, 1779, 1677, 1593, 1523, 1466, 1418, 1378, 1345, 1318, 1296, 1277, 1261, 1249, 1238, 1229, 1222, 1216, 1211, 1207, 1203, 1200, 1198, 1196, 1194, 1193, 1192, 1191, 1190, 1190, 1189, 1189, 1188, 1188, 1188, 1188, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187},
{INT_MAX, 38294, 31931, 26660, 22292, 18673, 15675, 13190, 11132, 9427, 8014, 6843, 5873, 5070, 4404, 3852, 3395, 3016, 2703, 2443, 2227, 2049, 1901, 1779, 1677, 1593, 1523, 1466, 1418, 1378, 1345, 1318, 1296, 1277, 1261, 1249, 1238, 1229, 1222, 1216, 1211, 1207, 1203, 1200, 1198, 1196, 1194, 1193, 1192, 1191, 1190, 1190, 1189, 1189, 1188, 1188, 1188, 1188, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187},
{INT_MAX, 38294, 31931, 26660, 22292, 18673, 15675, 13190, 11132, 9427, 8014, 6843, 5873, 5070, 4404, 3852, 3395, 3016, 2703, 2443, 2227, 2049, 1901, 1779, 1677, 1593, 1523, 1466, 1418, 1378, 1345, 1318, 1296, 1277, 1261, 1249, 1238, 1229, 1222, 1216, 1211, 1207, 1203, 1200, 1198, 1196, 1194, 1193, 1192, 1191, 1190, 1190, 1189, 1189, 1188, 1188, 1188, 1188, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187, 1187},
{INT_MAX, 32900, 28048, 23943, 20471, 17534, 15049, 12947, 11169, 9665, 8393, 7317, 6407, 5637, 4985, 4434, 3968, 3574, 3240, 2958, 2720, 2518, 2347, 2202, 2080, 1977, 1889, 1815, 1753, 1700, 1655, 1617, 1585, 1558, 1535, 1516, 1499, 1486, 1474, 1464, 1456, 1448, 1442, 1437, 1433, 1429, 1426, 1424, 1421, 1420, 1418, 1417, 1416, 1415, 1414, 1413, 1413, 1412, 1412, 1411, 1411, 1411, 1411, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1409, 1409, 1409, 1409},
{INT_MAX, 32900, 28048, 23943, 20471, 17534, 15049, 12947, 11169, 9665, 8393, 7317, 6407, 5637, 4985, 4434, 3968, 3574, 3240, 2958, 2720, 2518, 2347, 2202, 2080, 1977, 1889, 1815, 1753, 1700, 1655, 1617, 1585, 1558, 1535, 1516, 1499, 1486, 1474, 1464, 1456, 1448, 1442, 1437, 1433, 1429, 1426, 1424, 1421, 1420, 1418, 1417, 1416, 1415, 1414, 1413, 1413, 1412, 1412, 1411, 1411, 1411, 1411, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1410, 1409, 1409, 1409, 1409},
{INT_MAX, 43128, 35842, 29836, 24884, 20802, 17437, 14663, 12375, 10490, 8936, 7654, 6598, 5727, 5009, 4417, 3929, 3527, 3195, 2922, 2697, 2511, 2358, 2231, 2127, 2041, 1971, 1912, 1864, 1825, 1792, 1765, 1743, 1725, 1709, 1697, 1687, 1678, 1671, 1666, 1661, 1657, 1654, 1651, 1649, 1647, 1646, 1644, 1643, 1642, 1642, 1641, 1641, 1640, 1640, 1640, 1640, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639},
{INT_MAX, 43128, 35842, 29836, 24884, 20802, 17437, 14663, 12375, 10490, 8936, 7654, 6598, 5727, 5009, 4417, 3929, 3527, 3195, 2922, 2697, 2511, 2358, 2231, 2127, 2041, 1971, 1912, 1864, 1825, 1792, 1765, 1743, 1725, 1709, 1697, 1687, 1678, 1671, 1666, 1661, 1657, 1654, 1651, 1649, 1647, 1646, 1644, 1643, 1642, 1642, 1641, 1641, 1640, 1640, 1640, 1640, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639, 1639},
};
int calc_z(int y, int x) {
return y * GRID_SIZE + x;
}
bool is_inside(int y, int x) {
return 1 <= y && y <= N && 1 <= x && x <= N;
}
bool is_inside(int z) {
int y = z / GRID_SIZE;
int x = z % GRID_SIZE;
return is_inside(y, x);
}
double random_double(double min_v, double max_v) {
double range = max_v - min_v;
return min_v + range * xor128() / (double) ULLONG_MAX;
}
void apply_slope(vector<int> &positions, int off_x, int off_y, double s1, double s2) {
for (int z : positions) {
int y = z / GRID_SIZE;
int x = z % GRID_SIZE;
g_grid[z] += s1 * (x - off_x) + s2 * (y - off_y);
}
}
void apply_sincos(vector<int> &positions, int off_x, int off_y, double s1, double s2, double amp) {
for (int z : positions) {
int y = z / GRID_SIZE;
int x = z % GRID_SIZE;
g_grid[z] += amp * (sin((x - off_x) * s1) + cos((y - off_y) * s2));
}
}
void apply_xy2(vector<int> &positions, int off_x, int off_y, double rx, double ry, double amp) {
for (int z : positions) {
int y = z / GRID_SIZE;
int x = z % GRID_SIZE;
double dx = (double) (x - off_x) * (double) (x - off_x) * rx;
double dy = (double) (y - off_y) * (double) (y - off_y) * ry;
g_grid[z] += amp * fast_exp(-(dx + dy));
}
}
void apply_xor(vector<int> &positions, int off_x, int off_y) {
for (int z : positions) {
int y = z / GRID_SIZE;
int x = z % GRID_SIZE;
g_grid[z] += (x - off_x) ^ (y - off_y);
}
}
P apply_slope_all(int off_x, int off_y, double s1, double s2) {
double min_v = INT_MAX;
double max_v = INT_MIN;
for (int y = 1; y <= N; y++) {
for (int x = 1; x <= N; x++) {
int z = calc_z(y, x);
g_grid[z] += s1 * (x - off_x) + s2 * (y - off_y);
min_v = min(min_v, g_grid[z]);
max_v = max(max_v, g_grid[z]);
}
}
return P(min_v, max_v);
}
P apply_sincos_all(int off_x, int off_y, double s1, double s2, double amp) {
double min_v = INT_MAX;
double max_v = INT_MIN;
for (int y = 1; y <= N; y++) {
for (int x = 1; x <= N; x++) {
int z = calc_z(y, x);
g_grid[z] += amp * (sin((x - off_x) * s1) + cos((y - off_y) * s2));
min_v = min(min_v, g_grid[z]);
max_v = max(max_v, g_grid[z]);
}
}
return P(min_v, max_v);
}
P apply_xy2_all(int off_x, int off_y, double rx, double ry, double amp) {
double dx_values[N];
double dy_values[N];
// 事前計算
for (int i = 1; i <= N; i++) {
dx_values[i - 1] = (double) (i - off_x) * (double) (i - off_x) * rx;
dy_values[i - 1] = (double) (i - off_y) * (double) (i - off_y) * ry;
}
double min_v = INT_MAX;
double max_v = INT_MIN;
for (int x = 1; x <= N; x++) {
double dx = dx_values[x - 1];
for (int y = 1; y <= N; y++) {
int z = calc_z(y, x);
double dy = dy_values[y - 1];
g_grid[z] += amp * fast_exp(-(dx + dy));
// 最小値と最大値を更新
min_v = min(min_v, g_grid[z]);
max_v = max(max_v, g_grid[z]);
}
}
return P(min_v, max_v);
}
P apply_xor_all(int off_x, int off_y) {
double min_v = INT_MAX;
double max_v = INT_MIN;
for (int y = 1; y <= N; y++) {
for (int x = 1; x <= N; x++) {
int z = calc_z(y, x);
g_grid[z] += (x - off_x) ^ (y - off_y);
min_v = min(min_v, g_grid[z]);
max_v = max(max_v, g_grid[z]);
}
}
return P(min_v, max_v);
}
void undo_slope(vector<int> &positions, int off_x, int off_y, double s1, double s2) {
for (int z : positions) {
int y = z / GRID_SIZE;
int x = z % GRID_SIZE;
g_grid[z] -= s1 * (x - off_x) + s2 * (y - off_y);
}
}
void undo_sincos(vector<int> &positions, int off_x, int off_y, double s1, double s2, double amp) {
for (int z : positions) {
int y = z / GRID_SIZE;
int x = z % GRID_SIZE;
g_grid[z] -= amp * (sin((x - off_x) * s1) + cos((y - off_y) * s2));
}
}
void undo_xy2(vector<int> &positions, int off_x, int off_y, double rx, double ry, double amp) {
for (int z : positions) {
int y = z / GRID_SIZE;
int x = z % GRID_SIZE;
double dx = (double) (x - off_x) * (double) (x - off_x) * rx;
double dy = (double) (y - off_y) * (double) (y - off_y) * ry;
g_grid[z] -= amp * fast_exp(-(dx + dy));
}
}
void undo_xor(vector<int> &positions, int off_x, int off_y) {
for (int z : positions) {
int y = z / GRID_SIZE;
int x = z % GRID_SIZE;
g_grid[z] -= (x - off_x) ^ (y - off_y);
}
}
void undo_slope_all(int off_x, int off_y, double s1, double s2) {
for (int y = 1; y <= N; y++) {
for (int x = 1; x <= N; x++) {
int z = calc_z(y, x);
g_grid[z] -= s1 * (x - off_x) + s2 * (y - off_y);
}
}
}
void undo_sincos_all(int off_x, int off_y, double s1, double s2, double amp) {
for (int y = 1; y <= N; y++) {
for (int x = 1; x <= N; x++) {
int z = calc_z(y, x);
g_grid[z] -= amp * (sin((x - off_x) * s1) + cos((y - off_y) * s2));
}
}
}
void undo_xy2_all(int off_x, int off_y, double rx, double ry, double amp) {
double dx_values[N];
double dy_values[N];
for (int i = 1; i <= N; i++) {
dx_values[i - 1] = (double) (i - off_x) * (double) (i - off_x) * rx;
dy_values[i - 1] = (double) (i - off_y) * (double) (i - off_y) * ry;
}
// ループの順序を変更してベクトル化
for (int y = 1; y <= N; y++) {
for (int x = 1; x <= N; x++) {
int z = calc_z(y, x);
double dx = dx_values[x - 1];
double dy = dy_values[y - 1];
double exp_value = fast_exp(-(dx + dy));
g_grid[z] -= amp * exp_value;
}
}
}
void undo_xor_all(int off_x, int off_y) {
for (int y = 1; y <= N; y++) {
for (int x = 1; x <= N; x++) {
int z = calc_z(y, x);
g_grid[z] -= (x - off_x) ^ (y - off_y);
}
}
}
struct Node {
int z;
int dist;
Node(int z, int dist) {
this->z = z;
this->dist = dist;
}
};
struct Equation {
int type;
int off_x;
int off_y;
double v1;
double v2;
double amp;
bool activated;
Equation(int type = 0, int off_x = 0, int off_y = 0, double v1 = 0.0, double v2 = 0.0, double amp = 0.0) {
this->type = type;
this->off_x = off_x;
this->off_y = off_y;
this->v1 = v1;
this->v2 = v2;
this->amp = amp;
this->activated = true;
}
void apply() {
if (type == SLOPE) {
apply_slope(g_checked_positions, off_x, off_y, v1, v2);
} else if (type == SINCOS) {
apply_sincos(g_checked_positions, off_x, off_y, v1, v2, amp);
} else if (type == XOR) {
apply_xor(g_checked_positions, off_x, off_y);
} else {
apply_xy2(g_checked_positions, off_x, off_y, v1, v2, amp);
}
}
P apply_all() {
if (type == SLOPE) {
return apply_slope_all(off_x, off_y, v1, v2);
} else if (type == SINCOS) {
return apply_sincos_all(off_x, off_y, v1, v2, amp);
} else if (type == XOR) {
return apply_xor_all(off_x, off_y);
} else {
return apply_xy2_all(off_x, off_y, v1, v2, amp);
}
}
void undo() {
if (type == SLOPE) {
undo_slope(g_checked_positions, off_x, off_y, v1, v2);
} else if (type == SINCOS) {
undo_sincos(g_checked_positions, off_x, off_y, v1, v2, amp);
} else if (type == XOR) {
undo_xor(g_checked_positions, off_x, off_y);
} else {
undo_xy2(g_checked_positions, off_x, off_y, v1, v2, amp);
}
}
void undo_all() {
if (type == SLOPE) {
undo_slope_all(off_x, off_y, v1, v2);
} else if (type == SINCOS) {
undo_sincos_all(off_x, off_y, v1, v2, amp);
} else if (type == XOR) {
undo_xor_all(off_x, off_y);
} else {
undo_xy2_all(off_x, off_y, v1, v2, amp);
}
}
};
vector <Equation> g_equations;
class SurfaceReconstruction {
public:
void load_data() {
g_vid = 0;
memset(g_visited, -1, sizeof(g_visited));
memset(g_is_checked, false, sizeof(g_is_checked));
memset(g_correct_surface, 0, sizeof(g_correct_surface));
memset(g_grid, 0, sizeof(g_grid));
memset(g_is_wall, false, sizeof(g_is_wall));
g_checked_positions.clear();
cin >> A >> N;
for (int y = 0; y <= N + 1; y++) {
for (int x = 0; x <= N + 1; x++) {
int z = calc_z(y, x);
if (not is_inside(z)) {
g_is_wall[z] = true;
}
}
}
}
void normalize() {
double v_min = 1e30;
double v_max = -1e30;
for (int y = 1; y <= N; y++) {
for (int x = 1; x <= N; x++) {
int z = calc_z(y, x);
v_min = min(v_min, g_grid[z]);
v_max = max(v_max, g_grid[z]);
}
}
for (int y = 1; y <= N; y++) {
for (int x = 1; x <= N; x++) {
int z = calc_z(y, x);
g_surface[z] = 255 * (g_grid[z] - v_min) / (v_max - v_min);
}
}
}
Equation random_equation() {
int r = xor128() % 11;
int off_x = xor128() % N + 1;
int off_y = xor128() % N + 1;
double rx = random_double(0.001, 0.1);
double ry = random_double(0.001, 0.1);
double s1 = random_double(-10, 10);
double s2 = random_double(-10, 10);
double amp = random_double(10, 100);
if (r == 0) {
return Equation(SLOPE, off_x, off_y, s1, s2);
} else if (r == 1) {
s1 = random_double(-0.4, 0.4);
s2 = random_double(-0.4, 0.4);
return Equation(SINCOS, off_x, off_y, s1, s2, amp);
} else if (r == 2) {
return Equation(XOR, off_x, off_y, s1, s2, amp);
} else {
return Equation(XY2, off_x, off_y, rx, ry, amp);
}
}
vector<int> sa_pos(vector<int> sample_positions, double time_limit = TIME_LIMIT) {
ll start_cycle = get_cycle();
vector<int> cur_positions = sample_positions;
vector<int> best_positions = cur_positions;
int cur_score = calc_positions_score_full(cur_positions);
int best_score = cur_score;
double cur_time = get_time(start_cycle);
double total_diff = 0.0;
double t = 0.1;
ll R = 100000000;
int try_count = 0;
int L = sample_positions.size();
while (cur_time < time_limit) {
cur_time = get_time(start_cycle);
double remain_time = (time_limit - cur_time) / time_limit;
int idx = xor128() % L;
int y = xor128() % (N - 2) + 2;
int x = xor128() % (N - 2) + 2;
int z = calc_z(y, x);
int bz = cur_positions[idx];
cur_positions[idx] = z;
int score = calc_positions_score_full(cur_positions);
double diff_score = cur_score - score;
total_diff += fabs(diff_score);
if (diff_score > 0 || (xor128() % R < R * exp(diff_score / (t * sqrt(remain_time))))) {
cur_score = score;
if (best_score > score) {
best_score = score;
best_positions = cur_positions;
}
} else {
cur_positions[idx] = bz;
}
++try_count;
double average_diff = total_diff / try_count;
t = 0.25 * remain_time * average_diff;
}
fprintf(stderr, "try_count: %d, best_score: %d\n", try_count, best_score);
return best_positions;
}
void sa(double time_limit = TIME_LIMIT) {
ll start_cycle = get_cycle();
memset(g_grid, 0, sizeof(g_grid));
vector <Equation> equations;
for (int i = 0; i < MAX_E; ++i) {
Equation eq = random_equation();
eq.apply_all();
equations.push_back(eq);
}
int cur_score = calc_score_full_with_normalize(g_checked_positions);
int best_score = cur_score;
double cur_grid[GRID_SIZE * GRID_SIZE];
double best_grid[GRID_SIZE * GRID_SIZE];
memcpy(cur_grid, g_grid, sizeof(g_grid));
memcpy(best_grid, g_grid, sizeof(g_grid));
double cur_time = get_time(start_cycle);
double total_diff = 0.0;
double t = 0.1;
ll R = 100000000;
int try_count = 0;
while (cur_time < time_limit) {
cur_time = get_time(start_cycle);
double remain_time = (time_limit - cur_time) / time_limit;
int type = xor128() % 3;
int idx = xor128() % MAX_E;
Equation temp_eq = equations[idx];
if (type == 0) {
int dy;
int dx;
do {
dy = xor128() % 5 - 2;
dx = xor128() % 5 - 2;
} while (dy == 0 && dx == 0);
temp_eq.undo_all();
equations[idx].off_x = min(N, max(1, temp_eq.off_x + dx));
equations[idx].off_y = min(N, max(1, temp_eq.off_y + dy));
} else if (type == 1) {
temp_eq.undo_all();
equations[idx] = random_equation();
} else if (type == 2) {
if (temp_eq.type != XY2) continue;
double dx = random_double(-0.05, 0.05);
double dy = random_double(-0.05, 0.05);
temp_eq.undo_all();
equations[idx].v1 = min(0.1, max(0.001, temp_eq.v1 + dx));
equations[idx].v2 = min(0.1, max(0.001, temp_eq.v2 + dy));
}
P min_max = equations[idx].apply_all();
int score = calc_score_full(g_checked_positions, min_max.first, min_max.second);
double diff_score = cur_score - score;
total_diff += fabs(diff_score);
if (diff_score > 0 || (xor128() % R < R * exp(diff_score / (t * sqrt(remain_time))))) {
cur_score = score;
memcpy(cur_grid, g_grid, sizeof(g_grid));
if (best_score > score) {
best_score = score;
memcpy(best_grid, g_grid, sizeof(g_grid));
}
} else {
memcpy(g_grid, cur_grid, sizeof(cur_grid));
equations[idx] = temp_eq;
}
++try_count;
double average_diff = total_diff / try_count;
t = 0.25 * remain_time * average_diff;
}
fprintf(stderr, "try_count: %d\n", try_count);
fprintf(stderr, "EXP_MSE = %d\n", best_score);
memcpy(g_grid, best_grid, sizeof(g_grid));
}
int calc_score_full_with_normalize(vector<int> &positions) {
int score = 0;
normalize();
for (int z : positions) {
assert(g_is_checked[z]);
int diff = g_surface[z] - g_correct_surface[z];
score += diff * diff;
}
return score;
}
int calc_positions_score_full(vector<int> &sample_positions) {
++g_vid;
int score = 0;
queue <Node> que;
for (int sp : sample_positions) {
que.push(Node(sp, 0));
}
while (not que.empty()) {
Node node = que.front();
que.pop();
if (g_visited[node.z] == g_vid) continue;
g_visited[node.z] = g_vid;
score += node.dist;
int L = node.dist == 0 ? 8 : 4;
for (int dir = 0; dir < L; ++dir) {
int nz = node.z + DZ[dir];
if (g_is_wall[nz]) continue;
if (g_visited[nz] == g_vid) continue;
que.push(Node(nz, node.dist + 1));
}
}
return score;
}
int calc_score_full(vector<int> &positions, double min_v, double max_v) {
int score = 0;
for (int z : positions) {
int surface = 255 * (g_grid[z] - min_v) / (max_v - min_v);
assert(g_is_checked[z]);
int diff = surface - g_correct_surface[z];
score += diff * diff;
}
return score;
}
void run() {
load_data();
int max_samples = floor(N * N / 9);
double sample_cost = 100000 * (1.0 - A) * 1.0 / max_samples;
int sample_count = 0;
double cur_cost = 0;
int limit = 1000000;
int D = 1;
double cover_rate = sample_count * 9.0 / (N * N);
vector<int> sample_positions;
bool checked[GRID_SIZE * GRID_SIZE];
memset(checked, false, sizeof(checked));
while (limit > 0) {
if (N < 40) {
if (cur_cost > 4000 || cover_rate > 0.13) break;
}
if (N >= 40) {
if (g_exp_mse[N - 20][sample_count] < g_exp_mse[N - 20][sample_count + 1] + sample_cost) break;
}
--limit;
int y = xor128() % (N - 2) + 2;
int x = xor128() % (N - 2) + 2;
bool ok = true;
for (int dy = -D; dy <= D; ++dy) {
for (int dx = -D; dx <= D; ++dx) {
int ny = y + dy;
int nx = x + dx;
int nz = calc_z(ny, nx);
if (not is_inside(ny, nx)) continue;
if (checked[nz]) {
ok = false;
}
}
}
if (not ok) continue;
int z = calc_z(y, x);
sample_positions.push_back(z);
for (int dy = -1; dy <= 1; dy++) {
for (int dx = -1; dx <= 1; dx++) {
int ny = y + dy;
int nx = x + dx;
int nz = calc_z(ny, nx);
checked[nz] = true;
}
}
sample_count++;
cur_cost += sample_cost;
cover_rate = sample_count * 9.0 / (N * N);
}
sample_positions = sa_pos(sample_positions, 1.0);
int time = 0;
for (int z : sample_positions) {
time = send_query(z);
}
double remain_time = TIME_LIMIT - time * 1.0 / 1000;
fprintf(stderr, "time: %d\n", time);
fprintf(stderr, "sample_cost = %f\n", sample_cost);
fprintf(stderr, "sample_count = %d\n", sample_count);
fprintf(stderr, "cover_rate = %f\n", cover_rate);
int min_v = INT_MAX;
int max_v = 0;
for (int y = 1; y <= N; y++) {
for (int x = 1; x <= N; x++) {
int z = calc_z(y, x);
if (not g_is_checked[z]) continue;
min_v = min(min_v, g_correct_surface[z]);
max_v = max(max_v, g_correct_surface[z]);
}
}
fprintf(stderr, "min_v = %d\n", min_v);
fprintf(stderr, "max_v = %d\n", max_v);
sa(remain_time);
cout << "done" << endl;
normalize();
for (int y = 1; y <= N; y++) {
for (int x = 1; x <= N; x++) {
int z = calc_z(y, x);
if (g_is_checked[z]) {
cout << g_correct_surface[z] << endl;
} else {
cout << g_surface[z] << endl;
}
}
}
cout.flush();
}
int send_query(int z) {
int y = z / GRID_SIZE;
int x = z % GRID_SIZE;
assert(1 <= y - 1 && y + 1 <= MAX_N);
assert(1 <= x - 1 && x + 1 <= MAX_N);
cout << y - 1 << " " << x - 1 << endl;
cout.flush();
for (int dy = -1; dy <= 1; dy++) {
for (int dx = -1; dx <= 1; dx++) {
int ny = y + dy;
int nx = x + dx;
int nz = calc_z(ny, nx);
cin >> g_correct_surface[nz];
if (not g_is_checked[nz]) {
g_checked_positions.push_back(nz);
}
g_is_checked[nz] = true;
}
}
int time;
cin >> time;
return time;
}
};
int main() {
SurfaceReconstruction sr;
sr.run();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment