結果

問題 No.3067 ドーパミン
ユーザー furafura
提出日時 2023-09-15 02:11:30
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 27 ms / 2,000 ms
コード長 16,817 bytes
コンパイル時間 4,186 ms
コンパイル使用メモリ 269,124 KB
実行使用メモリ 4,812 KB
最終ジャッジ日時 2023-09-15 02:11:37
合計ジャッジ時間 5,870 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,384 KB
testcase_01 AC 3 ms
4,384 KB
testcase_02 AC 22 ms
4,380 KB
testcase_03 AC 2 ms
4,384 KB
testcase_04 AC 26 ms
4,812 KB
testcase_05 AC 26 ms
4,620 KB
testcase_06 AC 27 ms
4,556 KB
testcase_07 AC 21 ms
4,380 KB
testcase_08 AC 22 ms
4,388 KB
testcase_09 AC 6 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 2 ms
4,384 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef TEMPLATE_HPP
#define TEMPLATE_HPP

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define impl_overload4(a, b, c, d, e, ...) e
#define impl_overload5(a, b, c, d, e, f, ...) f
#define impl_overload6(a, b, c, d, e, f, g, ...) g
#define impl_overload7(a, b, c, d, e, f, g, h, ...) h

// clang-format off
#define impl_rep4(i, a, b, c) for (int i = (a); i < (b); i += (c))
#define impl_rep3(i, a, b) impl_rep4(i, a, b, 1)
#define impl_rep2(i, n) impl_rep3(i, 0, n)
#define impl_rep1(n) for (int _ = 0; _ < (n); ++_)
#define rep(...) impl_overload4(__VA_ARGS__, impl_rep4, impl_rep3, impl_rep2, impl_rep1)(__VA_ARGS__)

#define impl_rrep4(i, a, b, c) for (int i = (b) - 1; i >= (a); i -= (c))
#define impl_rrep3(i, a, b) impl_rrep4(i, a, b, 1)
#define impl_rrep2(i, n) impl_rrep3(i, 0, n)
#define rrep(...) impl_overload4(__VA_ARGS__, impl_rrep4, impl_rrep3, impl_rrep2)(__VA_ARGS__)
// clang-format on

#define all(v) std::begin(v), std::end(v)

template<typename T>
constexpr int bit(T x, unsigned int k) {
    return (x >> k) & 1;
}

template<typename T>
constexpr bool chmax(T& a, const T& b) {
    return a < b ? a = b, true : false;
}
template<typename T>
constexpr bool chmin(T& a, const T& b) {
    return a > b ? a = b, true : false;
}

void yesno(bool b) {
    std::cout << (b ? "Yes" : "No") << "\n";
}
void yes() {
    yesno(true);
}
void no() {
    yesno(false);
}

struct Setup {
    Setup() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        std::cout << std::fixed << std::setprecision(11);
    }
} setup;

#ifdef LOCAL
#include "template_local.hpp"
#else
#define show(...) ((void)0)
#endif

using uint = unsigned int;
using lint = long long;
using ulint = unsigned long long;

using namespace std;

#endif // TEMPLATE_HPP

// clang-format off
uint64_t a[29][29] = {
	{26426630, 14176228, 70225397, 44568705, 999301162, 613823, 57558942, 6718464, 959574529, 8573184, 134689, 2216425, 4200522, 7203856, 69022813, 7581311, 15539364, 210227181, 2244004, 16, 2206093, 5044516, 13189336, 42558358, 8695519, 31703281, 26789, 15546355, 55241078},
	{1624593, 4096, 77369616, 15054400, 66564, 528529, 496474, 5803281, 1020100, 25083945, 365267, 147456, 46444225, 31124641, 49266361, 30976, 94249, 149504965, 126493740, 268324, 17172736, 4656964, 27242468, 14175225, 34969, 1, 335241, 297493504, 22},
	{163489349, 134689, 8499552, 1686714, 3910187, 1359556, 4673318, 4804864, 4243600, 20684304, 14984641, 1700416, 549799368, 10150596, 174292804, 59979027, 6682225, 701932036, 8185286, 33373729, 1089, 2310400, 746011, 2656900, 8262810, 7776048, 2665831, 228251664, 52228131},
	{8847786, 1387684, 12086765, 35809765, 1372589, 15034928689, 13542866, 1079521, 7371068, 18757561, 78747876, 674041, 14055201, 30177375, 1774670, 1156, 22393459, 96179780, 22945292, 3663396, 69569752, 4835601, 3622220, 14025025, 1796519, 20116222, 270281, 25921, 4641882},
	{23132378, 537822481, 16935461, 2682934, 26829, 1985682721, 31888057, 9205156, 29537021, 24453909, 2085136, 34128964, 36864, 1590121, 5825787, 9388096, 3721, 2160900, 27393512, 177936989, 24324624, 26718561, 632510440, 484416, 46494896, 1602807, 20710695, 6765201, 240912624},
	{6458152, 544644, 29584, 267289, 16597476, 4225, 16702741, 14010049, 290463849, 391876, 10824100, 2815002, 75583386, 24007569, 11934592, 5564881, 37356544, 27878400, 62884230, 9891025, 10751841, 70756, 21822368, 5340721, 3385600, 15069924, 755161, 66049, 34263464},
	{5289938, 59431026, 4436148, 2459909, 82318684, 135443615, 11567240, 1909924, 23438537, 6874884, 10309523, 6012304, 17306338, 16703569, 12550896, 1, 196764677, 19847025, 13270937, 912402436, 227933151, 83759104, 2127319, 109175272, 13312734, 150289362, 341673, 20861726, 16442173},
	{105625, 49284, 355511025, 5329, 2832489, 135424, 266505625, 2989441, 9320809, 9991921, 147158694, 762068, 90383049, 18809569, 35074930, 28558814, 23833924, 11971600, 3013468, 91795079, 58430736, 4928400, 4, 3829849, 24542116, 62001, 9205156, 486334809, 13623481},
	{189127223, 14231187, 810000, 19321, 2, 135982167, 2582788, 7119501, 17847173828676242, 320510680554088, 24500379597492841, 334679191532383085, 6735482919480050, 25933343445080586, 21581617288276224, 41614577724152196, 3597896227441156, 237585195915605692, 819992478029118938, 5757151873740873, 34435069922004544, 2639126666849761, 20697314316134544, 81401057719394436, 455170744392893683, 96265958776, 20235491812777081, 7849195739570642, 17840524156980625},
	{13446889, 1476403776, 3341584, 31526786, 25172287, 1158046189, 4579600, 25614112, 18858594792906801, 97157512044087075, 8583768499201352, 51493082149240384, 438751524920563634, 58952187204511225, 980182635911571118, 10075279945981636, 242043483614867200, 1619512685727048, 987654321, 3013484410315369, 996411698904838542, 75727024186510096, 301910512736450, 15674484116928400, 768397452398157811, 19963682742652609, 83431307510937961, 723951695885999821, 1863130896000000},
	{24751326, 126736, 2603, 128444901, 216225, 2563131, 6058408, 14400, 14514459050969667, 65452835104725289, 4705736451472063, 81838777463450176, 10215129739505625, 24164303213566562, 60818182376684329, 166164519662083547, 54121438461461904, 10960800704100, 197320728219753648, 53490783932878009, 13052192158008481, 3514063554328, 6586200247646464, 14357311204712004, 22392822139274596, 273691129333161620, 51318159687273924, 4294967295, 66239079090333444},
	{289444, 18032320, 1375929, 9541921, 29944006, 11818835, 24285184, 1267876, 1680616261902400, 682098571722780488, 42525278968633472, 1895221345539600, 18504876111496, 4971008326922884, 34238445270232225, 70336000388259904, 17753028175440100, 61355174571854289, 119486243513795735, 43017139676983692, 115787985820277906, 37923540629626276, 85227135481523161, 384899706937321, 640502598789352953, 54976877278105225, 30148468695324736, 42583120954411682, 625274180063289},
	{23256069, 166627824, 212521, 7581530, 788544, 158404, 591444, 2430481, 166489929220005075, 363678664205484500, 3893172962927616, 244292675374420285, 16516049594, 79587262356501025, 200319175346305, 5725709599469095, 909850551074439044, 29884214442716, 86106059968832281, 9052519712983, 12822709891134025, 2557629320887207, 76781391744530263, 27745041930946752, 139887330317390908, 7471053610679, 15397813751724450, 8934659158102276, 6373212089760000},
	{75076, 839056, 649636, 929296, 31856709, 152631276, 1296, 1874161, 441795208155625, 87294051753326224, 23955110561676996, 3077505470622361, 38052544446336996, 39483196955179264, 17052155233289288, 838650461448390679, 63849192232536529, 33386595476480064, 20857620209805625, 11482694980044800, 22413160832037, 904498782032672, 31600666494972169, 480585181487065767, 10711320985800000, 6853331223952801, 76952279604702121, 53499522076331769, 66902225380076025},
	{7284601, 40804, 6403088, 1908576, 8905675, 64451368, 32959066, 4594852, 700979222216448, 72391696405561, 249235754127863009, 18034898498972480, 214540232815821675, 10493327086311364, 1211948378541698, 63293971988192849, 79079938665518025, 30002580549000900, 20213036921669868, 440358011814681, 12142518898028738, 1317773832873, 145378292978492523, 268899993881842510, 8694488293177600, 9363491351568225, 3333969266605156, 3142515396608449, 6927987983135296},
	{28875783, 63313849, 98, 497959225, 99443411, 12349867, 4583881, 236185569, 4131012615886116, 88126642124697124, 46851542330613241, 389977705427968567, 5192488383919929, 9095481533214756, 44225459404448448, 8096640288456889, 863708975349920813, 8729195724488, 128278530496733952, 38980992562576, 575715187374087, 7555995436702441, 13016829527525041, 64909617320248281, 371187618412900, 458059557857457548, 151893297101051427, 8444045934420100, 2196289721455},
	{101422375, 17424, 4803047, 106777563, 66049, 1490841, 13235, 37717705, 2879563665572356, 248494562623992428, 59768428885432, 33668074851561518, 12944083456996624, 373304264186349620, 12067964591986944, 497459113230000, 51646658535216144, 385560227813799821, 56431741344023447, 14503568615186562, 20987490164877604, 44824557514641147, 21249562281111616, 22898250232735684, 687089336786186322, 93010719039717675, 37942418315930769, 9149335897857319, 6774285701990401},
	{887068, 719104, 13521433, 567009, 1740944, 111325652, 160000, 1, 618817863602500, 912376554654012642, 3485714869443249, 75202055056264761, 975883560728816, 54081332683984225, 28650939147769689, 269395903678875627, 24939760786725625, 1399263898173696, 315758749752103691, 86065914704689262, 54491145232558225, 30, 34952213805837512, 1145141919893819, 93202136725531392, 36619012555787200, 49638592773434401, 34683260682611776, 891461160011827816},
	{36258077, 7744262, 13121607, 241081, 43811161, 6561, 12463011, 146635284, 101142234966475125, 70369247778144676, 67054732739140800, 2181050394259796, 41992642470892096, 77860086961231, 4369026725729689, 442319349884812766, 85041307549191184, 572574447321821935, 15559475510834423, 621668740882338891, 61659251010780267, 244199158881186963, 38438769139320050, 402473450810500989, 11514303747481746, 86941720193486596, 494038417687500, 517578421606074367, 1981507943278125},
	{12496430, 14641, 301948074, 3374569, 1085438916, 8094025, 25431849, 28999756, 15634300383542416, 7011729609833200, 3271575591389166, 2961134977456898, 26214160354378134, 22884291725251401, 2636061467648498, 40730155979608225, 85184600333280100, 9811779310189476, 682799486007364097, 21048509037967849, 94597344048818, 7434072567060624, 28601896405386304, 1126344009980401, 1635787795694847, 14357827881815716, 5655219729428025, 43783684710633169, 117853083392256},
	{224268983, 8100, 2426935, 8221786, 39106164, 81804852, 38632446, 16085719, 289651500760801, 68976389989876356, 57509482629577104, 9569637300177529, 16241050200450248, 80629740089767696, 3247482525045858, 486027415615521983, 5305078307, 19273068647840484, 376078473239836584, 471833858297169, 759108028415330539, 168580987666223405, 11416607275983845, 1400498632087296, 818920040381264156, 47647505633683396, 67476178712103529, 885711495574548219, 7330469664258244},
	{70879561, 34562641, 13579225, 4120900, 864900, 25, 14830368400, 23804641, 60397750160226675, 22616367371786881, 262514612128063743, 27323415249565681, 71853425689600, 354953931130768257, 161506726698908748, 3141592, 15352404996642328, 437827184169977451, 95903827767595575, 6692224744628361, 458073500457423692, 34175319272131041, 65283664546649124, 56646875076481600, 325704327140256980, 85580428588003584, 1015381220312209, 15513415681496769, 27541931405317128},
	{541716, 1350101, 27687184, 34776788, 480304, 38664013, 6021357, 3693479076, 320510680554107, 7711426804972900, 63640521214732900, 243155991349334173, 7410280467, 798994276313222182, 14848812597335616, 346161961289200500, 3179437618706568, 188262607181153967, 8738053451459378, 480332570033640505, 319809179126721310, 21990540397558084, 8932091665293228, 5791746060804484, 327673847425552348, 16957305696848400, 71037, 7700298501747687, 654046406097561},
	{4585394, 4393216, 169, 912025, 23409, 2916, 107014526, 2235025, 114514889464364387, 6444427738513303, 186137373704056428, 101, 19805185135112882, 20749448323769344, 30624752200501264, 2387988575702500, 6342404796729800, 22517554322601009, 243808716399151788, 35370913185406096, 1090525197129722, 9958513517691904, 57462737073238225, 24465581212641529, 1356919184887, 199226537104, 43622417726918416, 82548526671008836, 545262598564949},
	{2514932, 2856100, 3654569, 22970664, 925190, 3949242649, 16360651, 4571044, 28445577015209778, 338531447264966017, 66104653246495504, 58335142948462864, 24853322266508450, 619367882862427888, 1635787795694847, 3838101249160582, 569777233319585974, 26281435622041800, 127080750563260160, 296370435991154627, 396399699423758925, 563098692628060687, 21845133628648445, 756929056527999348, 6939328541811, 1529582713614400, 11489535756594018, 124611992446268047, 64604841155430976},
	{23717148, 1478656, 86032008, 3659753, 901237061, 155451024, 2263363952, 492884401, 34616216652321312, 138935911001462575, 1757031777164, 56309785053455241, 80127670138522, 699361563546396371, 1329535273360849, 960024969482731314, 3153897190265761, 67197727645310025, 408881930759706320, 13763018258878088, 39276911332513156, 34350353280741289, 19393374894969604, 33777763154496, 5873125849687684, 43579670220100, 645424593523264, 23972129236613538, 583767613286288014},
	{483, 189888400, 950476, 56248, 20915772, 103684, 9934918, 1890625, 37132469487932641, 19094389629316875, 964440414643586376, 3996248116333225, 42304996680786225, 54526, 273079343794295695, 917653059853096840, 27235567625280400, 7924014716794225, 2290283839787638, 202109440910400, 33257762809752100, 13107080177189067, 3, 36603489333907456, 2686010748428772, 878515888582, 291263422844662922, 334188698502708405, 7992151162964224},
	{17123620, 2414916, 236196, 207849889, 60516, 2637376, 48782711, 87025, 893, 204492526206016647, 542205425934485500, 474927570439200, 757359645583469827, 2181050394259444, 3074805610037, 11608214876513476, 3614048134225, 80263898822145600, 13878657083622, 39002661112555396, 28983092315164488, 19434932572737529, 854151322844516288, 85368513111356836, 29884214442763, 38134795503192976, 92462224886672368, 49412142999826929, 127697463132569643},
	{235492693, 28956667, 55209494, 21233244, 27346710, 38716356, 13941653, 47524, 464643937840190647, 72335929757839609, 75449813273514436, 17540331879846724, 33110907312216845, 69339424173087601, 839245612879765668, 13789290677797452, 45243154122001924, 44734576953261001, 1019002827782088, 31691722466499481, 45050869053610000, 218571815228469132, 12303992406108488, 3491729380994449, 392367542219582771, 59975021587672324, 551, 26332309569251912, 21039442803488}
};
// clang-format on

uint64_t f(uint64_t x) {
    uint64_t s = 0;
    for (uint64_t i = 1; i <= x; i++) {
        if (x % i) continue;
        s ^= i;
    }
    return s;
}

uint64_t g(uint64_t x) {
    if (x == 0) return 1;
    if (x == 1) return 0;
    bool t[x << 1] = {};
    for (uint64_t i = 1; i < x; i++) {
        t[g(i) ^ g(x - i)] = 1;
    }
    for (uint64_t i = 0;; i++) {
        if (!t[i]) return i;
    }
}

uint64_t f_fast(uint64_t x) {
    uint64_t s = 0;
    for (uint64_t i = 1; i * i <= x; i++) {
        if (x % i) continue;
        s ^= i;
        if (i * i < x) s ^= x / i;
    }
    return s;
}

uint64_t g_fast(uint64_t x) {
    return x % 2 == 0 ? 1 : 0;
}
/*
int main(void) {
    for (int i = 0; i < 29; i++) {
        for (int j = 0; j < 29; j++) {
            putchar(g_fast(f_fast(a[i][j])) ? '#' : ' ');
        }
        putchar('\n');
    }
    return 0;
}
*/

// The output of c.c is
/*
#######    ## ## #  # #######
#     #  ##  #   ##   #     #
# ### #     #  #  #   # ### #
# ### # #   ### ### # # ### #
# ### # ##    #   ##  # ### #
#     #    ####   #   #     #
####### # # # # # # # #######
          ##  ##  ##
##   ### # # #   ###    ##
   ### # #  # # # # #   #  #
# ## ## # #    #  #  #   # #
 #  ##   #  #     ###   #
## #  # ## ## #### # #####
    ##         #    #  ##
  ####### ###  #  #  ###
#   ## #   #  # # # #    ## #
# ##  ## ### # # ##  #  ## #
# # ##   #  #  #  ## #####  #
###   ### ## ### ##### ## ###
# #    # ## #     #     #
# ######    #  ## # #####  #
        # #  ###### #   #
####### #  ### # #### # # ##
#     # ####      # #   #   #
# ### #  #   #### #######  #
# ### #  ## ## #  #         #
# ### #  ##  ###  #  ## ####
#     # ### ###   #   # # # #
####### #   # ##     #  # #
*/
/*
This QR code tells a fragment of table
  L9 U
3  KB
8    V
 2  P
 D 1
 J7

Solve 6x6 magic square to obtain
NCL9AU
3WZKB4
8R0FOV
X2EQP5
GDS1IT
MJ7YH6

Table for ADFGVX cipher
 |ADFGVX
-+------
A|NCL9AU
D|3WZKB4
F|8R0FOV
G|X2EQP5
V|GDS1IT
X|MJ7YH6
*/

// txt.txt
/*
#######  #  #   # #######
#     #   ###   # #     #
# ### # ### # #   # ### #
# ### #  ###   ## # ### #
# ### #   #  #  # # ### #
#     #  #   ## # #     #
####### # # # # # #######
        ### ## ##
### ##### ## ##  ##   #
 # ### ## ##   #  ##   #
 ## # ## #    ### ## ##
 #  ##  #  # ### ##
  ### ###   #   #   #####
 #  #  ### ##   # ##  ##
#  # ## ######   # ### #
 ## #  #  # #   ### #  #
#    ## #  ##   ##### ##
        #  # # ##   # #
####### # # # ### # #   #
#     # ###   # #   #####
# ### # #   # # ##### # #
# ### #  #### #   ##  #
# ### # #### # ######## #
#     # #    #  ### # ###
####### ##    # # ##### #
*/
/*
This QR code says
AAFVVAAFXADVAAVAVGFGVFFFVVAVDAVGAVAV

key = dopamine
permutation = 27815463

solve ADFGVX cipher
27815463
--------
AAGAFVFD
AVAAGAFV
FDVFVVVA
XAAVFGVA
AVVV

plain text = NXORANXORSIGMAFGAI

N xor A_N xor Σ_i f(g(A_i))
*/

int main() {
    int n;
    cin >> n;
    vector<lint> A(n);
    rep (i, n) cin >> A[i];

    lint x = 0;
    rep (i, n) x += f_fast(g_fast(A[i]));

    cout << (n ^ A[n - 1] ^ x) << endl;

    return 0;
}
0