제출 #990482

#제출 시각아이디문제언어결과실행 시간메모리
990482AdamGS저울 (IOI15_scales)C++17
100 / 100
22 ms848 KiB
#include "scales.h" #include<bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; typedef struct item * pitem; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() int U[1500*6], L[1500]; struct item { pitem nxt[6]; int x=0; }; vector<vector<int>>A; int pytanie(vector<int>&P, vector<int>&V) { vector<pair<int,int>>C(3); rep(i, 3) C[i]={P[V[i]], V[i]}; sort(all(C)); if(V[3]==-1) return C[2].nd; // getHeaviest if(V[3]==-2) return C[0].nd; // getLightest if(V[3]==-3) return C[1].nd; // getMedian pair<int,int>mi={6, 6}; rep(i, 3) if(P[V[i]]>P[V[3]]) mi=min(mi, {P[V[i]], V[i]}); if(mi.st!=6) return mi.nd; return C[0].nd; } int zadaj(vector<int>&V) { if(V[3]==-1) return getHeaviest(V[0]+1, V[1]+1, V[2]+1)-1; if(V[3]==-2) return getLightest(V[0]+1, V[1]+1, V[2]+1)-1; if(V[3]==-3) return getMedian(V[0]+1, V[1]+1, V[2]+1)-1; return getNextLightest(V[0]+1, V[1]+1, V[2]+1, V[3]+1)-1; } int ocen(vector<vector<int>>&T, vector<int>&V) { vector<int>X(6); for(auto i : T) ++X[pytanie(i, V)]; int sum=0; for(auto i : X) sum+=i*i*i; return sum; } pair<int,pitem>licz(vector<vector<int>>&T, int d, pitem x) { bool czy=false; if(x!=nullptr) rep(i, 6) if(x->nxt[i]) czy=true; if(!czy) x=nullptr; if(x==nullptr) { x=new item(); rep(i, 6) x->nxt[i]=nullptr; } else { if(T.size()<=1) return {0, x}; if(d==0) return {2137, x}; vector<vector<int>>X[6]; for(auto j : T) X[pytanie(j, A[x->x])].pb(j); int ma=0; rep(j, 6) { pair<int,pitem>p=licz(X[j], d-1, x->nxt[j]); ma=max(ma, p.st); x->nxt[j]=p.nd; } return {ma+1, x}; } if(T.size()<=1) return {0, x}; if(d==0) return {2137, x}; vector<pair<int,int>>P; rep(i, A.size()) P.pb({ocen(T, A[i]), i}); sort(all(P)); int ans=2137; rep(i, 12-d) { int ma=0; vector<vector<int>>X[6]; for(auto j : T) X[pytanie(j, A[P[i].nd])].pb(j); rep(j, 6) { pair<int,pitem>p=licz(X[j], d-1, nullptr); ma=max(ma, p.st); x->nxt[j]=p.nd; if(ma>=d) break; } ans=min(ans, ma); if(ans<d) { x->x=P[i].nd; return {ans+1, x}; } } return {ans+1, x}; } int akt; void DFS(pitem x, int v, int d) { if(!x || d>3) return; cout << "pyt[" << v << "]=" << x->x << ";"; rep(i, 6) { ++akt; cout << "nxt[" << v << "][" << i << "]=" << akt << ";"; DFS(x->nxt[i], akt, d+1); } } pitem buduj(int v) { pitem x=new item(); x->x=L[v]; rep(i, 6) if(U[v*6+i]==-1) x->nxt[i]=nullptr; else x->nxt[i]=buduj(U[v*6+i]); return x; } pitem gora; void init(int _T) { rep(i, 1500*6) U[i]=-1; L[0]=3;U[0]=1;L[1]=96;U[6]=2;L[2]=38;U[12]=3;L[3]=0;U[18]=4;U[19]=5;U[20]=6;U[21]=7;U[22]=8;U[23]=9;U[13]=10;L[10]=16;U[60]=11;U[61]=12;U[62]=13;U[63]=14;U[64]=15;U[65]=16;U[14]=17;L[17]=10;U[102]=18;U[103]=19;U[104]=20;U[105]=21;U[106]=22;U[107]=23;U[15]=24;L[24]=0;U[144]=25;U[145]=26;U[146]=27;U[147]=28;U[148]=29;U[149]=30;U[16]=31;L[31]=1;U[186]=32;U[187]=33;U[188]=34;U[189]=35;U[190]=36;U[191]=37;U[17]=38;L[38]=0;U[228]=39;U[229]=40;U[230]=41;U[231]=42;U[232]=43;U[233]=44;U[7]=45;L[45]=0;U[270]=46;U[271]=47;U[272]=48;U[273]=49;U[274]=50;U[275]=51;U[8]=52;L[52]=0;U[312]=53;U[313]=54;U[314]=55;U[315]=56;U[316]=57;U[317]=58;U[9]=59;L[59]=0;U[354]=60;U[355]=61;U[356]=62;U[357]=63;U[358]=64;U[359]=65;U[10]=66;L[66]=37;U[396]=67;L[67]=0;U[402]=68;U[403]=69;U[404]=70;U[405]=71;U[406]=72;U[407]=73;U[397]=74;L[74]=29;U[444]=75;U[445]=76;U[446]=77;U[447]=78;U[448]=79;U[449]=80;U[398]=81;L[81]=35;U[486]=82;U[487]=83;U[488]=84;U[489]=85;U[490]=86;U[491]=87;U[399]=88;L[88]=0;U[528]=89;U[529]=90;U[530]=91;U[531]=92;U[532]=93;U[533]=94;U[400]=95;L[95]=4;U[570]=96;U[571]=97;U[572]=98;U[573]=99;U[574]=100;U[575]=101;U[401]=102;L[102]=0;U[612]=103;U[613]=104;U[614]=105;U[615]=106;U[616]=107;U[617]=108;U[11]=109;L[109]=41;U[654]=110;L[110]=0;U[660]=111;U[661]=112;U[662]=113;U[663]=114;U[664]=115;U[665]=116;U[655]=117;L[117]=26;U[702]=118;U[703]=119;U[704]=120;U[705]=121;U[706]=122;U[707]=123;U[656]=124;L[124]=32;U[744]=125;U[745]=126;U[746]=127;U[747]=128;U[748]=129;U[749]=130;U[657]=131;L[131]=0;U[786]=132;U[787]=133;U[788]=134;U[789]=135;U[790]=136;U[791]=137;U[658]=138;L[138]=4;U[828]=139;U[829]=140;U[830]=141;U[831]=142;U[832]=143;U[833]=144;U[659]=145;L[145]=0;U[870]=146;U[871]=147;U[872]=148;U[873]=149;U[874]=150;U[875]=151;U[1]=152;L[152]=102;U[912]=153;L[153]=0;U[918]=154;U[919]=155;U[920]=156;U[921]=157;U[922]=158;U[923]=159;U[913]=160;L[160]=32;U[960]=161;L[161]=22;U[966]=162;U[967]=163;U[968]=164;U[969]=165;U[970]=166;U[971]=167;U[961]=168;L[168]=0;U[1008]=169;U[1009]=170;U[1010]=171;U[1011]=172;U[1012]=173;U[1013]=174;U[962]=175;L[175]=10;U[1050]=176;U[1051]=177;U[1052]=178;U[1053]=179;U[1054]=180;U[1055]=181;U[963]=182;L[182]=0;U[1092]=183;U[1093]=184;U[1094]=185;U[1095]=186;U[1096]=187;U[1097]=188;U[964]=189;L[189]=1;U[1134]=190;U[1135]=191;U[1136]=192;U[1137]=193;U[1138]=194;U[1139]=195;U[965]=196;L[196]=0;U[1176]=197;U[1177]=198;U[1178]=199;U[1179]=200;U[1180]=201;U[1181]=202;U[914]=203;L[203]=0;U[1218]=204;U[1219]=205;U[1220]=206;U[1221]=207;U[1222]=208;U[1223]=209;U[915]=210;L[210]=0;U[1260]=211;U[1261]=212;U[1262]=213;U[1263]=214;U[1264]=215;U[1265]=216;U[916]=217;L[217]=31;U[1302]=218;L[218]=29;U[1308]=219;U[1309]=220;U[1310]=221;U[1311]=222;U[1312]=223;U[1313]=224;U[1303]=225;L[225]=0;U[1350]=226;U[1351]=227;U[1352]=228;U[1353]=229;U[1354]=230;U[1355]=231;U[1304]=232;L[232]=41;U[1392]=233;U[1393]=234;U[1394]=235;U[1395]=236;U[1396]=237;U[1397]=238;U[1305]=239;L[239]=0;U[1434]=240;U[1435]=241;U[1436]=242;U[1437]=243;U[1438]=244;U[1439]=245;U[1306]=246;L[246]=4;U[1476]=247;U[1477]=248;U[1478]=249;U[1479]=250;U[1480]=251;U[1481]=252;U[1307]=253;L[253]=0;U[1518]=254;U[1519]=255;U[1520]=256;U[1521]=257;U[1522]=258;U[1523]=259;U[917]=260;L[260]=35;U[1560]=261;L[261]=26;U[1566]=262;U[1567]=263;U[1568]=264;U[1569]=265;U[1570]=266;U[1571]=267;U[1561]=268;L[268]=0;U[1608]=269;U[1609]=270;U[1610]=271;U[1611]=272;U[1612]=273;U[1613]=274;U[1562]=275;L[275]=38;U[1650]=276;U[1651]=277;U[1652]=278;U[1653]=279;U[1654]=280;U[1655]=281;U[1563]=282;L[282]=0;U[1692]=283;U[1693]=284;U[1694]=285;U[1695]=286;U[1696]=287;U[1697]=288;U[1564]=289;L[289]=4;U[1734]=290;U[1735]=291;U[1736]=292;U[1737]=293;U[1738]=294;U[1739]=295;U[1565]=296;L[296]=0;U[1776]=297;U[1777]=298;U[1778]=299;U[1779]=300;U[1780]=301;U[1781]=302;U[2]=303;L[303]=108;U[1818]=304;L[304]=0;U[1824]=305;U[1825]=306;U[1826]=307;U[1827]=308;U[1828]=309;U[1829]=310;U[1819]=311;L[311]=0;U[1866]=312;U[1867]=313;U[1868]=314;U[1869]=315;U[1870]=316;U[1871]=317;U[1820]=318;L[318]=26;U[1908]=319;L[319]=22;U[1914]=320;U[1915]=321;U[1916]=322;U[1917]=323;U[1918]=324;U[1919]=325;U[1909]=326;L[326]=16;U[1956]=327;U[1957]=328;U[1958]=329;U[1959]=330;U[1960]=331;U[1961]=332;U[1910]=333;L[333]=0;U[1998]=334;U[1999]=335;U[2000]=336;U[2001]=337;U[2002]=338;U[2003]=339;U[1911]=340;L[340]=0;U[2040]=341;U[2041]=342;U[2042]=343;U[2043]=344;U[2044]=345;U[2045]=346;U[1912]=347;L[347]=1;U[2082]=348;U[2083]=349;U[2084]=350;U[2085]=351;U[2086]=352;U[2087]=353;U[1913]=354;L[354]=0;U[2124]=355;U[2125]=356;U[2126]=357;U[2127]=358;U[2128]=359;U[2129]=360;U[1821]=361;L[361]=0;U[2166]=362;U[2167]=363;U[2168]=364;U[2169]=365;U[2170]=366;U[2171]=367;U[1822]=368;L[368]=25;U[2208]=369;L[369]=35;U[2214]=370;U[2215]=371;U[2216]=372;U[2217]=373;U[2218]=374;U[2219]=375;U[2209]=376;L[376]=41;U[2256]=377;U[2257]=378;U[2258]=379;U[2259]=380;U[2260]=381;U[2261]=382;U[2210]=383;L[383]=0;U[2298]=384;U[2299]=385;U[2300]=386;U[2301]=387;U[2302]=388;U[2303]=389;U[2211]=390;L[390]=0;U[2340]=391;U[2341]=392;U[2342]=393;U[2343]=394;U[2344]=395;U[2345]=396;U[2212]=397;L[397]=4;U[2382]=398;U[2383]=399;U[2384]=400;U[2385]=401;U[2386]=402;U[2387]=403;U[2213]=404;L[404]=0;U[2424]=405;U[2425]=406;U[2426]=407;U[2427]=408;U[2428]=409;U[2429]=410;U[1823]=411;L[411]=29;U[2466]=412;L[412]=32;U[2472]=413;U[2473]=414;U[2474]=415;U[2475]=416;U[2476]=417;U[2477]=418;U[2467]=419;L[419]=38;U[2514]=420;U[2515]=421;U[2516]=422;U[2517]=423;U[2518]=424;U[2519]=425;U[2468]=426;L[426]=0;U[2556]=427;U[2557]=428;U[2558]=429;U[2559]=430;U[2560]=431;U[2561]=432;U[2469]=433;L[433]=0;U[2598]=434;U[2599]=435;U[2600]=436;U[2601]=437;U[2602]=438;U[2603]=439;U[2470]=440;L[440]=4;U[2640]=441;U[2641]=442;U[2642]=443;U[2643]=444;U[2644]=445;U[2645]=446;U[2471]=447;L[447]=0;U[2682]=448;U[2683]=449;U[2684]=450;U[2685]=451;U[2686]=452;U[2687]=453;U[3]=454;L[454]=0;U[2724]=455;U[2725]=456;U[2726]=457;U[2727]=458;U[2728]=459;U[2729]=460;U[4]=461;L[461]=0;U[2766]=462;U[2767]=463;U[2768]=464;U[2769]=465;U[2770]=466;U[2771]=467;U[5]=468;L[468]=0;U[2808]=469;U[2809]=470;U[2810]=471;U[2811]=472;U[2812]=473;U[2813]=474; ios_base::sync_with_stdio(0); cin.tie(0); rep(a, 6) rep(b, a) rep(c, b) { rep(i, 3) A.pb({a, b, c, -3+i}); rep(d, 6) if(a!=d && b!=d && c!=d) A.pb({a, b, c, d}); } vector<vector<int>>T; vector<int>P; rep(i, 6) P.pb(i); do T.pb(P); while(next_permutation(all(P))); pitem root=buduj(0); gora=licz(T, 6, root).nd; } void zejdz(pitem x, vector<vector<int>>T) { if(T.size()==1) { int ans[6]; rep(i, 6) ans[T[0][i]]=i+1; answer(ans); return; } vector<vector<int>>X[6]; for(auto j : T) X[pytanie(j, A[x->x])].pb(j); int p=zadaj(A[x->x]); zejdz(x->nxt[p], X[p]); } void orderCoins() { vector<vector<int>>T; vector<int>P; rep(i, 6) P.pb(i); do T.pb(P); while(next_permutation(all(P))); zejdz(gora, T); }

컴파일 시 표준 에러 (stderr) 메시지

scales.cpp: In function 'std::pair<int, item*> licz(std::vector<std::vector<int> >&, int, pitem)':
scales.cpp:7:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
scales.cpp:66:3: note: in expansion of macro 'rep'
   66 |   rep(i, A.size()) P.pb({ocen(T, A[i]), i});
      |   ^~~
scales.cpp: In function 'void init(int)':
scales.cpp:104:15: warning: unused parameter '_T' [-Wunused-parameter]
  104 | void init(int _T) {
      |           ~~~~^~

Subtask 1100 / 100

#Verdict Execution timeMemoryGrader output
Fetching results...