Submission #1099149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099149		jerzyk	Ancient Machine 2 (JOI23_ancient2)	C++17	97 / 100	31 ms	968 KiB

ancient2

#include <bits/stdc++.h>
#include "ancient2.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1003;
vector<int> ned = {1, 2, 3, 4, 6, 5, 10, 8, 9, 11, 12, 13, 18, 19, 20, 17, 21, 22, 23, 24, 25, 26, 30, 32, 31, 34, 35, 33, 38, 39, 40, 41, 48, 49, 47, 50, 53, 54, 55, 51, 52, 56, 59, 60, 57, 58, 68, 71, 72, 69, 70, 74, 75, 73, 77, 76, 78, 79, 84, 85, 80, 81, 82, 83, 94, 95, 93, 96, 97, 98, 99, 100, 107, 110, 111, 108, 109, 112, 113, 114, 122, 123, 124, 125, 126, 127, 128, 129, 130, 132, 131, 133, 137, 134, 135, 136, 138, 139, 140, 141, 142, 143, 155, 156, 157, 158, 159, 160, 161, 162, 163, 165, 166, 167, 164, 168, 170, 171, 172, 169, 174, 173, 178, 179, 180, 175, 176, 177, 195, 192, 193, 194, 201, 202, 203, 196, 197, 198, 199, 200, 214, 212, 213, 217, 218, 219, 220, 221, 215, 216, 234, 233, 235, 239, 240, 236, 237, 238, 241, 242, 244, 243, 246, 247, 248, 249, 245, 253, 254, 250, 251, 252, 256, 257, 255, 259, 258, 261, 262, 260, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 289, 288, 290, 291, 292, 293, 294, 295, 296, 297, 302, 303, 304, 306, 305, 313, 307, 308, 309, 310, 311, 312, 330, 331, 332, 333, 334, 335, 336, 327, 328, 329, 338, 339, 340, 341, 342, 337, 343, 344, 355, 353, 354, 356, 364, 357, 358, 359, 360, 361, 362, 363, 380, 381, 382, 383, 384, 385, 387, 388, 389, 390, 386, 391, 392, 395, 396, 393, 394, 397, 398, 399, 401, 400, 402, 404, 403, 405, 406, 407, 409, 408, 413, 414, 415, 410, 411, 412, 437, 439, 440, 438, 441, 444, 445, 446, 442, 443, 448, 449, 447, 451, 452, 450, 454, 455, 453, 456, 458, 459, 457, 460, 461, 462, 464, 465, 463, 466, 467, 468, 470, 469, 471, 472, 473, 474, 477, 475, 476, 478, 479, 480, 481, 482, 499, 498, 501, 502, 503, 504, 505, 506, 507, 500, 509, 510, 508, 511, 512, 513, 514, 515, 516, 517, 537, 538, 539, 530, 531, 532, 533, 534, 535, 536, 540, 542, 543, 544, 541, 545, 563, 564, 565, 566, 567, 568, 569, 570, 571, 572, 575, 573, 574, 578, 576, 577, 579, 580, 581, 582, 583, 584, 585, 586, 598, 599, 597, 601, 602, 600, 603, 604, 605, 606, 607, 608, 632, 633, 634, 635, 638, 636, 637, 639, 643, 644, 645, 646, 640, 641, 642, 647, 648, 649, 650, 651, 653, 654, 652, 655, 656, 657, 659, 658, 661, 660, 662, 663, 664, 665, 667, 666, 669, 668, 672, 670, 671, 674, 673, 678, 679, 680, 681, 682, 683, 684, 685, 675, 676, 677, 706, 705, 707, 708, 709, 710, 711, 712, 713, 714, 715, 716, 718, 719, 720, 721, 717, 723, 722, 724, 725, 726, 728, 727, 743, 744, 745, 746, 747, 748, 749, 750, 751, 752, 755, 753, 754, 756, 758, 757, 782, 783, 786, 787, 788, 789, 784, 785, 790, 791, 792, 793, 795, 796, 797, 794, 798, 799, 800, 801, 804, 805, 806, 807, 802, 803, 808, 809, 810, 811, 813, 814, 815, 812, 818, 819, 820, 821, 816, 817, 822, 823, 825, 824, 826, 827, 828, 829, 830, 831, 832, 833, 863, 864, 865, 866, 870, 871, 872, 873, 874, 867, 868, 869, 875, 878, 876, 877, 879, 880, 881, 882, 883, 884, 885, 887, 886, 889, 888, 891, 890, 892, 893, 894, 897, 895, 896, 899, 898, 900, 901, 902, 903, 904, 905, 906, 907, 908, 909, 910, 924, 911, 912, 913, 914, 915, 916, 917, 918, 919, 920, 921, 922, 923, 950, 951, 948, 949, 952, 953, 954, 955, 956, 958, 957, 959, 960, 967, 961, 962, 963, 964, 965, 966, 969, 968, 970, 971, 992, 993, 994, 997, 998, 995, 996, 1000, 1001, 1002, 1003, 999, 1006, 1004, 1005, 1009, 1010, 1011, 1007, 1008, 1013, 1012, 1037, 1038, 1039, 1042, 1040, 1041, 1043, 1044, 1045, 1047, 1046, 1051, 1048, 1049, 1050, 1052, 1053, 1058, 1054, 1055, 1056, 1057, 1061, 1062, 1063, 1064, 1065, 1066, 1067, 1068, 1069, 1070, 1059, 1060, 1071, 1072, 1073, 1074, 1075, 1076, 1077, 1078, 1080, 1079, 1082, 1081, 1088, 1089, 1090, 1091, 1092, 1083, 1084, 1085, 1086, 1087, 1096, 1097, 1098, 1093, 1094, 1095, 1133, 1130, 1131, 1132, 1136, 1134, 1135, 1137, 1139, 1138, 1140, 1141, 1144, 1142, 1143, 1147, 1148, 1145, 1146, 1150, 1149, 1154, 1151, 1152, 1153, 1155, 1156, 1157, 1158, 1159, 1160, 1161, 1164, 1162, 1163, 1165, 1166, 1167, 1169, 1168, 1170, 1171, 1183, 1178, 1179, 1180, 1181, 1182, 1184, 1185, 1186, 1187, 1188, 1189, 1190, 1191, 1192, 1193, 1194, 1195, 1196, 1197, 1230, 1227, 1228, 1229, 1231, 1232, 1235, 1236, 1233, 1234, 1238, 1239, 1237, 1243, 1240, 1241, 1242, 1244, 1245, 1246, 1247, 1251, 1248, 1249, 1250, 1253, 1254, 1255, 1252, 1256, 1258, 1257, 1279, 1280, 1277, 1278, 1282, 1281, 1288, 1289, 1290, 1291, 1292, 1283, 1284, 1285, 1286, 1287, 1294, 1293, 1296, 1295, 1298, 1297, 1300, 1299, 1328, 1329, 1330, 1331, 1335, 1332, 1333, 1334, 1337, 1338, 1339, 1336, 1340, 1341, 1343, 1342, 1344, 1345, 1346, 1347, 1348, 1349, 1350, 1351, 1352, 1353, 1354, 1355, 1356, 1357, 1358, 1364, 1359, 1360, 1361, 1362, 1363, 1365, 1366, 1367, 1368, 1369, 1370, 1371, 1372, 1373, 1374, 1375, 1376, 1377, 1378, 1379, 1380, 1383, 1381, 1382, 1387, 1384, 1385, 1386, 1390, 1391, 1392, 1388, 1389, 1394, 1393, 1395, 1396, 1397, 1434, 1433, 1435, 1436, 1437, 1438, 1439, 1440, 1441, 1442, 1445, 1443, 1444, 1450, 1446, 1447, 1448, 1449, 1451, 1452, 1453, 1456, 1457, 1458, 1459, 1454, 1455, 1462, 1463, 1460, 1461, 1464, 1466, 1465, 1467, 1471, 1468, 1469, 1470, 1472, 1488, 1489, 1487, 1490, 1495, 1491, 1492, 1493, 1494, 1497, 1496, 1498, 1499, 1500, 1501, 1502, 1504, 1505, 1503, 1510, 1506, 1507, 1508, 1509, 1542, 1543, 1544, 1545, 1546, 1547, 1549, 1548, 1553, 1550, 1551, 1552, 1555, 1554, 1561, 1562, 1563, 1564, 1565, 1566, 1567, 1568, 1569, 1570, 1556, 1557, 1558, 1559, 1560, 1571, 1572, 1573, 1574, 1575, 1576, 1577};
bitset<N> eq[N * 10];
pair<int, int> wh[N * 10];
string answer;
int cnt = 0;

void Gen(int n)
{
    for(int i = 1; i <= 61; ++i)
        for(int j = 0; j < i - 1 + (i == 1); ++j)
        {
            ++cnt;
            wh[cnt] = make_pair(i, j);
            for(int l = j; l < n; l += i)
                eq[cnt][l] = 1;
        }
}

void Fix(int n)
{
    for(int i = 0; i < n; ++i)
    {
        eq[i] = eq[ned[i]];
        wh[i] = wh[ned[i]];
    }
}

void DoQ(int r, int n)
{
    int m = wh[r].st * 2;
    //cerr << m << "\n";
    vector<int> qa(m, 0), qb(m, 0);
    for(int i = 0; i < (m / 2); ++i)
    {
        int c0 = i * 2, c1 = i * 2 + 1;
        int n0 = (c0 + 2) % m, n1 = (c1 + 2) % m;
        qa[c0] = n0; qa[c1] = n1;
        qb[c0] = n0; qb[c1] = n1;
        if(i == wh[r].nd)
        {
            qb[c0] = n1;
            qb[c1] = n0;
        }
    }
    int ans = Query(m, qa, qb);
    eq[r][n] = (ans % 2);
}

void Elimination(int n)
{
    for(int i = 0; i <= n - 1; ++i)
        for(int j = i + 1; j <= n - 1; ++j)
            if(eq[j][i] == 1)
                eq[j] = eq[j] ^ eq[i];

    for(int i = n - 1; i >= 0; --i)
        for(int j = i - 1; j >= 0; --j)
            if(eq[j][i] == 1)
                eq[j] = eq[j] ^ eq[i];

    for(int i = 0; i < n; ++i)
        answer.pb('0' + eq[i][n]);
}

string Solve(int _N)
{
    int n = _N;
    Gen(1000);
    Fix(n);
    for(int i = 0; i < n; ++i)
        DoQ(i, n);
    Elimination(n);
    while((int)answer.size() > n)
        answer.pop_back();
    return answer;
}

• Subtask 1: 97 / 100