Submission #990482

#	Time	Username	Problem	Language	Result	Execution time	Memory
990482		AdamGS	Scales (IOI15_scales)	C++17	100 / 100	22 ms	848 KiB

scales

#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);
}

Compilation message (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 1: 100 / 100