TrianglePath
SRM 771 · 2019-11-26 · by misof
SRM 771 · 2019-11-26 · by misof · Geometry, Math, Recursion
Problem Statement
Problem Statement
Given is a right triangle. The three vertices of the triangle are at (0, 0), (Xmax,0), and (0, Ymax).
Also given is a collection of N (not necessarily distinct) points that all lie inside or on the boundary of the triangle. Points are numbered 0 through N-1, with point i having coordinates (X[i], Y[i]).
Your task is to construct a polyline with the following properties.
- The polyline visits each of the given points exactly once.
- The sum of squares of lengths of the segments of the polyline must not exceed Xmax^2 + Ymax^2.
Return a permutation of 0 through N-1 that corresponds to one possible order in which the polyline should visit the N points.
Any valid solution will be accepted
If there is no solution, return an empty
The input is generated pseudorandomly as follows:
X = Xprefix
Y = Yprefix
state = seed
while length(X) < N:
state = (state * 1103515245 + 12345) modulo 2^31
xnew = state modulo (Xmax + 1)
state = (state * 1103515245 + 12345) modulo 2^31
ynew = state modulo (Ymax + 1)
if point (xnew, ynew) lies inside the triangle or on its boundary:
X.append(xnew)
Y.append(ynew)
Notes
- Note that one of the constraints implies that the triangle cannot be long and narrow, so there should not be any too-degenerate test cases.
Constraints
- N will be between 1 and 3000, inclusive.
- Xmax will be between 3 and 10^6, inclusive.
- Ymax will be between 3 and 10^6, inclusive.
- 20*Xmax >= Ymax and 20*Ymax >= Xmax.
- Xprefix will have between 0 and min(N,500) elements.
- Yprefix will have the same number of elements as Xprefix.
- Each point (Xprefix[i], Yprefix[i]) will lie inside the triangle or on its boundary.
- seed will be between 0 and 2^31 - 1, inclusive.
Examples
0)
3
40
30
{0, 40, 0}
{0, 0, 30}
47
Returns: {2, 0, 1 }
The three points are in the corners of the triangle. We can visit them in the order {1, 0, 2}. If we do so, the first segment of the polyline has length 40 and the second segment has length 30. This exactly satisfies the constraints, as 40^2 + 30^2 = 40^2 + 30^2. The reverse order {2, 0, 1} is also a valid solution, but the other four permutations are not. For example, if we visit the points in order {0, 1, 2}, the sum of squares of polyline segment lengths will be 40^2 + 50^2, which is too big.
1)
5
7
7
{5, 2, 4, 1, 3}
{1, 4, 2, 5, 3}
47
Returns: {3, 1, 4, 2, 0 }
2)
3
54321
12345
{47, 47, 47}
{47, 47, 47}
47474747
Returns: {0, 1, 2 }
3)
10
12
14
{4, 7}
{7, 4}
1
Returns: {6, 5, 0, 8, 9, 3, 4, 7, 1, 2 }
The arrays X and Y you are supposed to obtain look as follows: X = {4, 7, 9, 0, 0, 1, 2, 5, 5, 4, }; Y = {7, 4, 0, 1, 0, 7, 11, 4, 5, 5, };
4)
3000
1000000
50000
{}
{}
47
Returns: {314, 278, 221, 2272, 1858, 1432, 2884, 1959, 1798, 1327, 240, 2657, 1925, 481, 2527, 2232, 2094, 2815, 709, 1226, 1292, 2511, 2774, 1054, 2184, 1271, 2827, 317, 883, 823, 300, 71, 1638, 357, 2100, 1869, 1134, 1928, 1265, 2692, 617, 2457, 1364, 651, 2851, 986, 1010, 818, 263, 2482, 2383, 2999, 324, 388, 48, 977, 2813, 1217, 2196, 875, 1897, 1781, 2776, 1030, 1634, 953, 2468, 1690, 2666, 204, 1053, 2415, 2266, 10, 501, 1055, 1637, 337, 1814, 333, 2800, 2316, 2862, 2261, 923, 259, 27, 2616, 2299, 951, 1299, 1487, 1543, 1486, 1588, 816, 2798, 750, 2949, 2369, 2194, 1696, 1137, 1012, 1389, 2291, 488, 995, 2981, 1509, 2681, 2985, 2313, 1447, 2326, 2655, 2267, 1876, 2451, 2140, 978, 311, 2384, 2886, 710, 1016, 2238, 2515, 1258, 1911, 2756, 2680, 2480, 1820, 494, 2931, 714, 1186, 2940, 1422, 538, 1131, 773, 120, 2319, 2410, 320, 2489, 1997, 1755, 1071, 2572, 2013, 694, 1658, 2244, 2180, 1527, 485, 1842, 1542, 299, 974, 1585, 385, 635, 1514, 2587, 997, 2758, 305, 2151, 2335, 1081, 480, 2822, 1377, 2063, 2893, 807, 2990, 369, 1383, 2784, 1576, 184, 1662, 1442, 376, 1435, 234, 2224, 222, 2773, 2216, 1456, 505, 1254, 238, 584, 2440, 1880, 2004, 427, 1045, 634, 1532, 959, 2307, 832, 59, 1002, 1082, 2571, 828, 1294, 788, 925, 1564, 284, 1611, 815, 915, 2268, 1172, 633, 1721, 2665, 2339, 777, 1009, 1747, 2227, 130, 1609, 1128, 1401, 1551, 735, 2460, 558, 1444, 1713, 878, 315, 553, 319, 190, 2249, 1971, 1666, 1720, 1656, 101, 1783, 2716, 2343, 1237, 117, 2504, 1968, 1489, 1517, 457, 206, 2934, 1079, 2549, 2347, 726, 914, 626, 211, 2467, 1099, 1404, 1001, 2874, 1130, 1889, 1535, 2293, 2295, 2664, 2703, 824, 1495, 355, 1917, 939, 2133, 1640, 2937, 1347, 2166, 1466, 2526, 830, 1915, 1190, 906, 650, 33, 794, 1481, 1728, 261, 2603, 2578, 1771, 727, 1061, 583, 964, 1392, 2785, 2454, 143, 885, 2988, 2679, 291, 2376, 2223, 1712, 2065, 1277, 1321, 1960, 296, 1852, 2279, 948, 243, 1050, 2435, 1138, 1735, 965, 2178, 1474, 460, 1256, 783, 1033, 2872, 2744, 1734, 2079, 163, 1109, 2464, 1066, 479, 733, 798, 2563, 983, 2255, 68, 756, 178, 398, 1305, 2121, 107, 255, 2461, 75, 1196, 1024, 2709, 1477, 310, 1752, 2769, 2085, 1199, 2378, 1855, 350, 435, 1007, 2898, 2363, 468, 2787, 2290, 1659, 686, 2282, 711, 2857, 2686, 934, 1427, 2582, 1028, 472, 698, 352, 2824, 2589, 45, 356, 2195, 2512, 254, 1507, 2411, 416, 532, 399, 842, 847, 519, 2170, 2915, 1415, 2257, 2897, 1097, 89, 949, 2683, 2548, 2023, 2803, 760, 2071, 1085, 674, 2057, 2626, 1788, 2154, 2957, 371, 2521, 897, 1692, 2328, 1892, 636, 1155, 144, 486, 1689, 582, 1628, 2705, 2479, 52, 1546, 1746, 1847, 392, 2923, 1667, 280, 459, 2309, 2323, 72, 2581, 1848, 852, 1613, 1825, 1428, 358, 1714, 1570, 2259, 715, 1995, 822, 2569, 841, 2157, 301, 2786, 219, 2165, 474, 831, 1348, 228, 1945, 1669, 2687, 2101, 970, 1075, 2837, 2519, 2271, 1239, 1813, 1195, 124, 1049, 666, 35, 2056, 1051, 85, 752, 1188, 2477, 387, 1865, 1388, 1700, 2288, 2108, 868, 1617, 482, 768, 528, 2398, 2444, 1807, 245, 1693, 2345, 1345, 1040, 909, 2250, 131, 441, 2072, 198, 1180, 2607, 1717, 2840, 1019, 1325, 1579, 2794, 2487, 2674, 1452, 1331, 2532, 2513, 287, 1708, 1062, 1682, 2018, 681, 1801, 729, 405, 1890, 776, 683, 1246, 731, 292, 2831, 2974, 2324, 1661, 1372, 930, 625, 2055, 2520, 2839, 1618, 4, 2871, 2276, 1281, 2381, 2458, 1730, 194, 2635, 2792, 901, 1935, 412, 1649, 2763, 141, 560, 1991, 2228, 880, 439, 1560, 1178, 283, 277, 2599, 2969, 1090, 1274, 803, 1257, 2653, 2176, 2405, 706, 2707, 1340, 2301, 2256, 1606, 365, 2710, 2814, 2475, 471, 2274, 627, 1937, 2733, 2832, 2134, 1777, 2780, 2624, 2849, 2541, 1753, 354, 1619, 1515, 2701, 56, 375, 1441, 1652, 656, 1859, 2825, 2336, 2916, 892, 1335, 1291, 2972, 1267, 396, 767, 622, 367, 1821, 598, 568, 2522, 1657, 1643, 2359, 1989, 2124, 700, 2185, 2027, 2675, 189, 2177, 849, 1660, 826, 2842, 2193, 2153, 1313, 2325, 1339, 1919, 2761, 1118, 303, 152, 784, 28, 95, 1136, 2034, 98, 2951, 2233, 2637, 2090, 1873, 1630, 413, 1646, 1093, 1015, 1895, 2910, 1278, 758, 1805, 173, 799, 2084, 1996, 2297, 503, 2930, 2163, 1063, 1984, 2009, 409, 608, 2718, 2096, 1963, 2986, 168, 2329, 1241, 1259, 1448, 1921, 620, 751, 2322, 705, 1849, 723, 786, 2594, 499, 212, 159, 1886, 2826, 1076, 2070, 2518, 2880, 1261, 1520, 1853, 2738, 2502, 2493, 2568, 1126, 556, 49, 63, 26, 888, 1946, 2917, 1104, 1382, 2509, 2719, 2991, 2495, 2618, 2145, 1169, 273, 1856, 2485, 858, 1938, 1775, 2561, 103, 2021, 1221, 738, 2992, 2843, 1311, 313, 2472, 1070, 32, 1870, 785, 2976, 664, 2150, 1903, 1744, 1975, 92, 1896, 34, 1706, 1232, 1641, 233, 549, 80, 2818, 904, 2750, 2836, 1597, 414, 2669, 1758, 2841, 2633, 844, 1140, 2912, 2120, 18, 1391, 1037, 2869, 2551, 2206, 988, 1497, 982, 2567, 2650, 1433, 1830, 2418, 125, 1243, 2583, 187, 1039, 2770, 899, 1253, 2245, 2093, 592, 2338, 2446, 1396, 920, 2481, 360, 1501, 1355, 2046, 332, 1837, 2492, 2437, 2115, 230, 2641, 2254, 271, 2863, 1031, 266, 1704, 1718, 680, 1059, 2673, 2970, 146, 2491, 887, 525, 2882, 2712, 2116, 1341, 857, 2807, 115, 1023, 1147, 2670, 2459, 1434, 594, 971, 1750, 1554, 2036, 1900, 493, 1288, 2375, 1760, 879, 1992, 2365, 1419, 1304, 2829, 1080, 1252, 2947, 2726, 1373, 2922, 1295, 2828, 272, 2387, 1881, 2819, 202, 537, 2534, 1574, 2739, 1948, 1480, 2743, 341, 724, 814, 19, 2667, 2401, 1539, 854, 585, 1955, 2073, 2929, 1387, 1146, 1013, 2168, 361, 2408, 1229, 2711, 563, 526, 2191, 1934, 1687, 2574, 1862, 1381, 44, 936, 2025, 2846, 1789, 2396, 2429, 58, 557, 2649, 1129, 1376, 882, 1334, 950, 90, 764, 2380, 1812, 1926, 800, 1871, 2175, 1685, 1393, 465, 2403, 1233, 1207, 1314, 2118, 2845, 407, 1872, 2209, 765, 515, 1829, 434, 1936, 2062, 282, 1967, 1827, 1280, 1986, 487, 1249, 663, 1289, 1850, 2593, 2590, 707, 1653, 648, 2152, 1449, 199, 1780, 2556, 1914, 2868, 1011, 2388, 2447, 511, 363, 2478, 1756, 2994, 991, 2537, 410, 792, 2539, 377, 2682, 2933, 216, 13, 2631, 1309, 1205, 2155, 2771, 836, 429, 215, 2651, 872, 2982, 1360, 2921, 1916, 2202, 2225, 2613, 2298, 2129, 2749, 1868, 1359, 623, 2765, 1248, 593, 649, 716, 149, 947, 1684, 616, 1200, 2713, 2327, 1273, 1202, 2939, 791, 2989, 1462, 2130, 531, 2971, 88, 840, 1116, 249, 2796, 244, 2555, 2500, 2496, 2432, 2741, 1962, 492, 2688, 809, 1739, 1014, 573, 1874, 1189, 1875, 2782, 329, 2035, 39, 241, 1211, 394, 1893, 41, 2684, 567, 264, 2088, 232, 1005, 1930, 1175, 114, 2205, 1133, 1791, 2625, 845, 77, 771, 2514, 2281, 2010, 2821, 2330, 1083, 451, 449, 138, 1269, 344, 2139, 2503, 61, 607, 960, 639, 2314, 76, 2617, 2049, 1491, 1794, 601, 2634, 2560, 2473, 1737, 1046, 774, 2908, 561, 2565, 127, 1125, 848, 2579, 817, 805, 1767, 1809, 438, 1533, 99, 274, 2442, 1279, 2685, 2167, 2586, 2795, 2357, 339, 1390, 82, 1406, 2742, 2745, 1725, 1426, 2935, 393, 603, 1215, 1431, 2622, 1571, 295, 662, 1673, 1642, 2031, 962, 876, 739, 14, 1025, 1668, 1565, 1193, 2043, 2204, 1663, 470, 641, 2538, 1296, 2919, 235, 2926, 1096, 2395, 2131, 2300, 2693, 521, 2775, 1748, 220, 335, 676, 1177, 1622, 2998, 1929, 1655, 2552, 734, 685, 1183, 372, 2207, 1490, 1018, 2173, 1650, 464, 1216, 523, 996, 1552, 2077, 316, 162, 2110, 1702, 1888, 851, 2892, 884, 37, 1885, 2995, 972, 258, 2696, 1203, 497, 1957, 1665, 520, 2054, 1823, 1164, 408, 1754, 1586, 1878, 864, 581, 267, 2214, 2965, 2958, 2040, 2791, 1639, 15, 1589, 22, 1318, 1161, 2764, 2901, 922, 2689, 1312, 2867, 2217, 148, 2864, 1354, 1260, 1724, 2033, 935, 2661, 1742, 1802, 1578, 2349, 921, 379, 571, 1336, 2544, 624, 229, 2698, 637, 1224, 1276, 2517, 736, 1522, 122, 1534, 200, 2239, 1990, 1135, 1979, 1123, 643, 1513, 1695, 697, 2001, 1598, 2351, 1153, 484, 2212, 166, 2883, 1593, 2663, 2545, 389, 93, 860, 1471, 1121, 2801, 247, 1998, 2258, 2900, 2777, 2277, 349, 338, 536, 2466, 450, 1458, 570, 2789, 2099, 946, 1627, 498, 362, 1776, 2230, 1901, 919, 2393, 2536, 1223, 1927, 2136, 630, 2530, 1838, 2676, 1098, 611, 2636, 1375, 2848, 265, 400, 1058, 1368, 453, 1445, 2936, 1048, 1536, 720, 1308, 86, 404, 907, 551, 2237, 850, 1518, 749, 2781, 193, 1337, 109, 1590, 2700, 804, 1453, 1741, 1436, 446, 2221, 2436, 297, 579, 252, 1352, 2296, 679, 157, 1089, 2847, 1577, 218, 2562, 1499, 1044, 2162, 170, 1799, 2413, 253, 214, 2945, 2332, 1184, 1947, 307, 1541, 1238, 447, 312, 2147, 2531, 2942, 1100, 621, 2320, 772, 1815, 2211, 2950, 829, 224, 1988, 719, 336, 2608, 81, 136, 2628, 918, 2925, 2606, 164, 604, 1816, 2927, 589, 811, 1654, 1264, 2076, 116, 2097, 2471, 1679, 1699, 2087, 2080, 976, 1380, 1086, 1866, 466, 2289, 1545, 455, 2348, 1973, 999, 1285, 1384, 1421, 1111, 423, 2647, 2612, 2138, 1732, 70, 886, 2426, 1933, 2333, 1150, 2114, 670, 1167, 1222, 562, 1567, 2566, 2252, 612, 2983, 1113, 1845, 642, 2944, 1124, 177, 179, 2727, 11, 1158, 111, 1879, 917, 2629, 699, 55, 1162, 172, 2811, 2805, 596, 961, 2146, 1759, 1266, 2368, 1819, 958, 2609, 2752, 2455, 2068, 2302, 1440, 2648, 386, 2966, 1170, 2699, 2766, 1607, 1353, 1726, 100, 2799, 673, 1020, 1156, 1247, 364, 1182, 1810, 833, 990, 1899, 1976, 1525, 2602, 778, 535, 853, 1531, 1472, 1584, 1594, 2128, 495, 2218, 2242, 2423, 1558, 2508, 2677, 1877, 2003, 789, 2525, 406, 2715, 2723, 1465, 2061, 2678, 1459, 1218, 980, 619, 881, 1782, 1779, 513, 2215, 279, 891, 1275, 1623, 2144, 931, 2433, 1686, 956, 2366, 17, 675, 2066, 384, 2430, 16, 613, 2660, 1074, 1105, 2967, 2598, 431, 1790, 281, 2092, 2483, 1766, 1187, 2907, 2189, 1904, 2417, 2516, 1450, 1460, 638, 665, 1398, 846, 489, 257, 1841, 2311, 902, 1839, 1369, 2753, 1417, 186, 2226, 1290, 351, 1631, 609, 2104, 1496, 1287, 517, 894, 2938, 819, 2979, 1069, 916, 2074, 1912, 1317, 769, 820, 782, 2420, 23, 454, 180, 1114, 856, 1954, 644, 1966, 2285, 2064, 2048, 1201, 770, 672, 1537, 940, 1455, 2439, 2441, 248, 693, 967, 2292, 1165, 1953, 701, 2377, 1423, 1719, 2251, 2024, 62, 2278, 2751, 1785, 223, 448, 2078, 2484, 2283, 304, 1307, 2973, 391, 747, 2008, 1603, 508, 766, 1824, 209, 2543, 2961, 183, 541, 2402, 1409, 587, 1329, 1961, 2340, 36, 1143, 1691, 476, 2720, 2968, 985, 2890, 559, 2488, 2051, 1410, 1591, 1366, 1403, 2044, 2029, 2172, 2615, 835, 1060, 2143, 1310, 1035, 2834, 945, 1493, 2977, 2007, 1034, 1425, 605, 1151, 2235, 181, 1715, 1524, 524, 1566, 753, 2371, 1284, 2391, 43, 1793, 104, 2419, 564, 1483, 1950, 1021, 1350, 989, 1412, 615, 84, 2860, 1616, 1219, 2658, 1500, 1599, 566, 2352, 1969, 712, 2334, 2037, 530, 1818, 2877, 1965, 606, 1629, 1484, 871, 1575, 2105, 550, 2652, 60, 2361, 1944, 1127, 2284, 251, 1711, 2535, 1467, 1003, 1179, 2909, 1363, 91, 276, 30, 325, 1861, 1430, 436, 1298, 140, 2181, 1283, 578, 128, 900, 2107, 1306, 600, 66, 2779, 2505, 2853, 1688, 797, 1770, 2006, 877, 192, 2714, 1400, 653, 1510, 2201, 1572, 2735, 2052, 2523, 2904, 2755, 1286, 861, 2507, 572, 2265, 1676, 1394, 1970, 323, 2002, 547, 2924, 924, 2889, 1315, 2160, 171, 678, 97, 79, 1173, 210, 47, 1723, 2011, 2854, 1612, 1088, 2342, 2905, 874, 839, 1587, 1733, 2443, 2920, 2470, 2754, 539, 1555, 1672, 2353, 2614, 1073, 2219, 1763, 2802, 469, 1000, 225, 2932, 2806, 1978, 2350, 542, 67, 1358, 1424, 2833, 540, 2269, 2494, 2394, 827, 2865, 1835, 718, 227, 2234, 2858, 1822, 1504, 2722, 1047, 2975, 1197, 2275, 108, 126, 322, 327, 151, 467, 2895, 1117, 655, 787, 2132, 713, 2220, 345, 1236, 2639, 2476, 890, 2262, 1402, 2645, 1941, 790, 1918, 1036, 2404, 2611, 2748, 256, 496, 2604, 2315, 2809, 1891, 2399, 2694, 102, 123, 73, 2577, 169, 269, 2580, 1795, 1234, 2875, 461, 677, 754, 1065, 118, 250, 1475, 2736, 129, 979, 1635, 1320, 1324, 1553, 812, 1367, 2734, 703, 1907, 1894, 640, 2984, 2499, 2453, 1272, 2671, 1605, 24, 1596, 1840, 759, 2911, 1250, 1765, 112, 1943, 425, 1149, 1338, 955, 2697, 937, 1498, 969, 1446, 42, 2554, 2852, 2812, 1174, 2946, 1910, 1482, 1176, 929, 1240, 137, 704, 2627, 702, 1644, 998, 2861, 2240, 2941, 745, 1806, 2960, 912, 2354, 2546, 1610, 913, 2372, 270, 737, 1027, 433, 1883, 343, 1351, 2102, 837, 500, 1103, 1804, 2431, 2591, 2082, 1052, 1909, 226, 213, 2725, 1300, 368, 569, 2573, 825, 2370, 2389, 1145, 1316, 1333, 452, 1681, 1540, 689, 1181, 2888, 231, 1293, 1709, 2708, 2030, 174, 1068, 801, 1761, 1157, 1212, 64, 1106, 2229, 2644, 2654, 896, 2817, 2312, 1204, 246, 1463, 2896, 2053, 1769, 158, 1371, 2367, 1323, 544, 808, 757, 1828, 631, 2406, 1152, 2208, 2280, 165, 866, 1110, 597, 1508, 1905, 2125, 1581, 1740, 2095, 2083, 602, 2767, 1831, 1418, 1166, 2213, 2997, 855, 1159, 1139, 65, 2032, 2198, 2187, 1974, 2702, 1530, 1451, 1698, 294, 456, 1854, 646, 1395, 1548, 838, 2287, 2528, 374, 546, 2158, 1538, 903, 1454, 1884, 1745, 1228, 1, 326, 1408, 1374, 1319, 2906, 2014, 2768, 1562, 518, 742, 2308, 201, 3, 565, 1519, 728, 992, 83, 1330, 1797, 1437, 2098, 203, 780, 2463, 2993, 2856, 2498, 1621, 2360, 1485, 910, 1362, 987, 2668, 1707, 1302, 2169, 762, 2605, 1722, 2042, 2103, 1846, 905, 2113, 1041, 2835, 2576, 591, 442, 2263, 1479, 155, 2020, 208, 236, 1902, 2069, 2881, 1056, 1949, 506, 2, 543, 1887, 590, 2963, 1414, 2757, 1626, 2575, 440, 1633, 2956, 207, 2619, 2732, 2643, 2610, 1008, 1242, 834, 687, 286, 717, 509, 1413, 298, 865, 2164, 1983, 29, 1882, 1505, 1600, 688, 191, 2192, 2304, 1438, 722, 968, 1811, 908, 2247, 370, 2630, 113, 2830, 359, 755, 534, 2996, 2914, 586, 2474, 1478, 302, 420, 1981, 2706, 147, 2601, 2346, 1057, 54, 401, 1494, 1042, 1834, 1087, 2081, 2672, 522, 721, 1636, 2656, 2434, 867, 2788, 1632, 334, 1808, 2588, 8, 328, 1738, 38, 2584, 2816, 2243, 2273, 1072, 1529, 105, 1148, 1924, 2294, 1378, 1282, 1549, 1457, 478, 1743, 2149, 1357, 1270, 2959, 795, 2557, 217, 806, 645, 1860, 1664, 1163, 1160, 1220, 2452, 743, 2341, 1067, 185, 2524, 1787, 741, 428, 1077, 599, 2620, 1356, 973, 2253, 318, 2717, 595, 1826, 954, 1332, 1386, 1095, 1956, 1701, 444, 2397, 2067, 821, 2456, 1301, 2060, 462, 51, 1231, 1004, 2465, 288, 1084, 1094, 692, 463, 2337, 1987, 306, 1705, 1102, 2691, 628, 993, 421, 796, 1784, 2141, 175, 1952, 1343, 2804, 1836, 1361, 483, 2156, 504, 1112, 21, 2762, 289, 1792, 2089, 1262, 397, 781, 1547, 1512, 119, 1864, 1800, 1683, 2558, 2000, 1762, 775, 2039, 437, 746, 2127, 1476, 2623, 331, 1144, 2310, 402, 1303, 1370, 682, 1778, 1645, 1624, 2550, 1851, 262, 2891, 2188, 2174, 2179, 732, 154, 1268, 1464, 419, 1972, 2746, 1022, 1964, 2148, 1191, 2640, 1230, 2490, 1521, 2142, 2870, 1582, 2038, 50, 2362, 744, 1857, 1101, 205, 2050, 275, 2759, 942, 793, 142, 2501, 1908, 382, 938, 378, 1213, 1198, 242, 94, 2962, 2595, 237, 1469, 2248, 966, 2355, 2704, 268, 2954, 2091, 1245, 1675, 1225, 342, 2730, 1461, 2597, 2823, 1736, 133, 1710, 424, 502, 2728, 1694, 1751, 2690, 2866, 574, 293, 2373, 1803, 182, 1006, 2592, 1107, 2186, 1346, 932, 2075, 2356, 1141, 2210, 417, 1503, 2894, 1980, 2564, 1931, 514, 1774, 1608, 46, 2321, 2200, 381, 96, 2600, 1573, 1119, 2913, 957, 139, 1429, 610, 529, 2506, 1939, 1559, 2331, 2364, 1677, 2236, 156, 2740, 188, 1297, 348, 1817, 2902, 2122, 418, 2540, 2344, 1506, 952, 1120, 2783, 1544, 2421, 1208, 2045, 1832, 1132, 1468, 1556, 239, 629, 2392, 1923, 1977, 1601, 445, 1982, 426, 2306, 5, 1064, 1843, 2414, 2427, 668, 1244, 690, 430, 1091, 647, 1399, 510, 512, 1932, 2382, 2109, 1043, 2019, 132, 2123, 810, 975, 1727, 2422, 390, 321, 1922, 2412, 1906, 1210, 2286, 2646, 1647, 1328, 2878, 2270, 1488, 1379, 196, 2642, 197, 1420, 577, 2026, 1942, 121, 2111, 7, 527, 2903, 1115, 862, 443, 1993, 933, 2778, 1416, 1026, 2570, 1142, 432, 395, 873, 2425, 1029, 1764, 2885, 1557, 1108, 669, 1411, 2638, 1569, 1729, 895, 2873, 1615, 660, 491, 1583, 78, 1674, 1999, 893, 545, 2106, 2955, 2086, 1017, 31, 576, 667, 458, 869, 981, 2632, 1365, 870, 618, 2808, 2948, 1032, 1550, 2793, 1703, 1122, 153, 2918, 2264, 2542, 1604, 53, 580, 1171, 1470, 57, 373, 366, 761, 2659, 2028, 725, 2059, 548, 347, 588, 2409, 2305, 1154, 12, 2859, 2953, 1322, 1592, 2416, 1561, 1620, 1898, 167, 2137, 1192, 2760, 1951, 380, 941, 1526, 1867, 1595, 1092, 2724, 161, 2469, 2424, 2978, 1614, 1326, 2171, 9, 2844, 2737, 353, 2943, 1568, 1648, 2058, 1397, 1651, 1038, 2246, 2012, 473, 1443, 2850, 2980, 691, 1255, 898, 1528, 2445, 654, 1078, 2449, 2529, 2379, 2303, 2317, 1680, 2952, 657, 422, 290, 1940, 2005, 859, 1516, 1671, 2876, 2928, 2987, 632, 2260, 843, 614, 2879, 2747, 1580, 2374, 2838, 346, 2790, 1214, 1768, 1523, 963, 2729, 1209, 1625, 176, 2462, 2450, 2126, 2448, 145, 927, 2041, 1185, 661, 2559, 2964, 2119, 889, 2486, 2438, 2022, 20, 1194, 659, 1563, 748, 106, 1920, 911, 1439, 684, 2585, 2497, 928, 2695, 1405, 1602, 2318, 1731, 2899, 74, 2662, 2241, 2385, 943, 2135, 2358, 260, 552, 2190, 1407, 2820, 2183, 1349, 1227, 763, 1697, 1796, 383, 2553, 1502, 195, 1773, 2161, 730, 2400, 340, 134, 2797, 1385, 1206, 477, 1833, 1235, 2731, 1757, 2855, 2015, 25, 2390, 110, 69, 2016, 2772, 555, 1786, 2017, 2510, 403, 1492, 1473, 802, 2159, 2721, 309, 1958, 575, 1994, 1772, 1678, 1168, 135, 0, 308, 2197, 696, 2407, 1985, 695, 926, 554, 475, 2386, 87, 658, 2810, 2112, 740, 411, 2887, 2596, 2547, 507, 1716, 2182, 1251, 2047, 984, 813, 330, 1342, 1263, 2428, 2203, 2117, 671, 944, 1913, 40, 2231, 652, 285, 1511, 150, 1670, 994, 1344, 2621, 2199, 160, 1844, 1863, 863, 1749, 2222, 2533, 490, 533, 415, 516, 779, 708, 6 }
Submissions are judged against all 48 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TrianglePath with a public method vector<int> construct(int N, int Xmax, int Ymax, vector<int> Xprefix, vector<int> Yprefix, int seed) · 48 test cases · 2 s / 256 MB per case