| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1071084 | GrindMachine | How to Avoid Disqualification in 75 Easy Steps (CEOI23_avoid) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
refs:
edi
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
struct chash {
const int RANDOM = (long long)(make_unique<char>().get()) ^ chrono::high_resolution_clock::now().time_since_epoch().count();
static unsigned long long hash_f(unsigned long long x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
static unsigned hash_combine(unsigned a, unsigned b) { return a * 31 + b; }
int operator()(int x) const { return hash_f(x)^RANDOM; }
};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int B = 26;
void solve(int test_case)
{
ll n = 1000;
auto f = [&](vector<ll> &b){
gp_hash_table<ll,ll,chash> mp;
ll res = 0;
rep(i,n){
rep(j,i){
ll x = b[i]^b[j];
res += mp[x]++;
}
}
return res;
};
auto p = [&](ll old_cost, ll new_cost, ld temp) -> ld{
if(new_cost < old_cost){
return 1;
}
return exp((old_cost-new_cost)/temp);
};
ld temp = 1;
ld alpha = 0.999;
vector<ll> a(n);
rep(i,n) a[i] = rng()%(1ll<<B);
ll cost = f(a);
uniform_real_distribution<ld> dist(0,1);
cerr << cost << endl;
while(cost){
temp *= alpha;
auto b = a;
ll i = rng()%n;
b[i] = rng()%(1ll<<B);
ll nxt_cost = f(b);
if(p(cost,nxt_cost,temp) >= dist(rng)){
a = b;
cost = nxt_cost;
cerr << temp << " " << cost << endl;
}
}
debug(a);
// after ~30 mins of running, found a valid array
// vector<ll> a = {36966892,2171277,32070394,44351801,49139726,32503053,67074223,40102625,25860440,7528512,63869402,4481375,33741462,28599417,27549773,54667160,47981047,5585648,17126347,60667599,60261393,43467787,15111493,25897002,26424925,34727956,14976729,50751542,16707468,40203184,49420496,4777536,24420568,17875975,46120602,6271257,41885658,63230737,48319309,7621228,22832162,34563633,57026323,18885481,22855678,33113557,65327611,17076441,47743905,56697640,1437888,13134070,38246550,34678573,50194598,63008251,49733616,55206033,52402489,13440331,49811859,62385096,24412310,61200320,24471530,57527130,11680748,36388375,39004817,27382874,22113553,36297328,7399814,2729001,42762597,43359975,6799853,59287761,54099174,33770153,59784218,7861535,1369256,52455483,52340092,65799633,10325861,8852334,6004978,62875925,9670140,65852242,33794221,42806231,52106943,46668118,34639077,35506900,38957684,14444897,61699461,18385458,65314444,10099449,35145473,65127959,28367748,15436573,45747065,63688359,99861,537764,30348734,14007388,46301503,46375599,8813687,35664824,16935300,18394247,6598033,15853024,10069913,42775663,12874440,30515038,58538177,14598348,53118040,59042318,60024543,55818938,16566555,42803701,50096947,36836111,17785854,48949513,59458807,14640464,8207394,49559960,26462618,27809359,46466279,6234453,2102388,60770994,34645579,12304662,63013203,62132272,40707536,30206846,14824609,167657,63404492,14762424,49209262,6454332,37946759,21774749,57836503,34310399,29556131,54311240,15482852,24444439,28247813,53487788,39835264,20792307,41190126,49364204,61687482,29147985,50647243,9692154,27387193,61154320,58759365,35021282,36440027,30025676,59662376,46115295,32029964,60073429,54535528,20671609,5851283,38110096,46562643,66432028,25218230,43919632,60620312,19570303,52265349,1903777,53348674,1594786,37053755,30648338,29788824,54690261,7026808,62667214,51863535,21384890,64776183,26392914,11909417,5878853,32465378,3424798,20446050,46772050,28264677,27605059,8698304,8461517,49874225,64027103,27526113,66501683,38804006,4355305,59045695,54721988,52057186,39592166,40523292,35966170,42043751,26234865,11687149,26768961,14093839,13547497,2720669,43469842,14361750,5428157,36601726,37823478,3945792,30522852,12440208,19922751,13772272,21051228,29256163,34584106,38424070,57830793,27032833,66035917,25822081,43135143,19066114,38861729,25202880,64080370,24480013,65851996,49009407,4452184,3692610,27790228,24524381,66465113,36661889,51300582,27014957,29019603,13848602,35349605,28849794,17730444,2090147,19684775,60255012,26510886,61911188,52798087,22595027,20256749,53972895,54511564,53146477,17847316,35350217,34350824,8950339,55514401,4276375,4610931,4152436,7929650,13319117,27119531,54506392,10665204,20087963,62687523,64641750,18374594,54218862,54323300,4002611,1324133,35907252,1489516,51635157,56579320,440368,19081752,44582960,43646282,24128158,1846259,39724429,32166714,26878101,39437389,65884890,12967584,36461393,10292864,54230775,63160335,11326907,21203644,28982057,3450629,54120138,35614054,58414916,46715549,29098098,58994890,15397293,44039795,64837952,4964675,25733936,47232277,51826708,22768740,28976077,42509496,34508163,60918415,26606120,63295280,21569846,13070436,38464816,1621588,10193440,64694628,51266186,22727076,22612110,46501286,12087212,7381713,65104825,1549621,65285472,19241424,62050379,17508031,14268999,36287283,27772957,8128442,63314498,30616340,38329327,26760922,40698334,21206762,33982282,20128435,28821807,51302200,721735,48656304,3000840,10823349,26124511,37718728,20466367,56009170,17542521,1848585,57301959,41690457,2540637,13196536,37484097,47596612,35905859,19904434,55242901,38585879,20465458,59098365,24349653,66310185,13191942,49012646,6346081,7301412,38128129,14407437,29353385,47959844,14776488,63466722,17883715,21667822,52330092,31115292,63511374,43031605,36176521,29837622,46955713,59212139,44637076,48282850,61858749,17994870,66566472,13945385,41328232,63677891,57679826,14743822,49693282,2020040,1941340,65302468,7937358,4558051,20886282,58481574,23196495,22500334,6595870,44883060,1642249,5434050,17947118,32727063,6826484,45311776,45827372,28055604,60884952,49109458,1051071,57775773,4242018,24395619,11375616,2979338,8240963,44815651,45818428,37345353,8790541,39173309,60423210,43530354,16380805,56771122,4835666,3266927,43933239,19005114,57541708,424401,54394204,10947303,43705502,56309089,25765144,63724845,4147066,45931012,47427928,1132583,17871106,20447691,10722460,4619616,47047180,58671132,37585552,57952674,60950292,96207,27681447,56807173,15795243,12302185,40026012,18167495,36846410,31609256,21134546,35350685,1310759,32056039,31176830,30306272,38385657,25928825,59256769,17505140,27956603,29302385,61633739,5341083,42814443,442098,4721398,61836384,17623476,59297060,17291315,5275885,36999907,9980617,31919180,12931901,2017915,62085368,15471580,66915740,64345632,44792355,27496798,11964319,61026741,59855209,60013258,9744189,25022714,30725412,18911197,35994880,54807762,8577071,31001605,19423158,49180411,7244676,8789301,1428349,58300186,53179900,66404794,51550189,26517612,23703154,42654553,21423838,50114862,56579116,62766397,5049563,64640174,46170638,30475506,23874064,52344371,34526567,16106828,31419418,27100126,6804005,34443381,53556584,11782857,28596731,20944438,46550153,12791017,10717045,30750029,6393450,27850423,26789413,10134030,1199768,43808773,65690837,34412651,14267251,18564470,28486275,25073253,36053629,53559560,10522112,45046802,13045422,6825726,5360775,57690780,66995519,12760884,27403298,36075403,63946166,7493892,6448686,27760534,44413518,40261763,62587551,39047427,17738651,51226407,11062056,20874112,13978319,20485957,23672797,26115288,2039766,46244967,36778606,32989886,40234668,31258561,46224095,43641909,42053741,43781243,22569796,39622707,50639335,6926810,10442749,65105481,31426334,55179354,41999756,38033939,27707347,60370531,64732657,5972891,17501114,64866335,57984841,3499403,26373541,28536941,52476271,47640905,32622920,28909202,23824210,34610191,13113962,18431369,18434310,14803571,55276687,25451874,25950348,52349073,66048389,30090290,45746909,31149695,65042519,25220383,58181286,60140115,6615155,20296538,47538229,24776329,6802542,30796447,40962125,12048672,31049654,47867250,23140669,58179608,28631636,43401619,61650234,30777842,18642499,37936540,27969657,18681548,19570288,54019896,17595524,36702750,23194385,46451146,35993557,7736835,45991500,54590165,59764838,34976335,50539219,62420064,40628678,5539080,56196296,28785292,43044941,51098539,10264907,62768801,27210262,50782306,43812605,63645038,31273685,36217087,20187858,38956379,29204050,47384120,4871899,17228888,26184621,36706338,22279110,38044573,4465599,11121623,59356388,64831404,32828375,60858542,54270431,9470835,56817800,52359277,38279894,20780973,40270746,26444398,40125821,60745838,13267735,1463955,13035664,2691537,39157365,7516545,46636227,54826343,37534702,3541577,42305133,57076652,59722975,28380776,12723926,35183457,5893861,51608796,48902971,60272272,46107817,55408165,26742077,11545011,51557985,61590422,60368435,42536510,12430228,29432457,37776531,13287054,51018489,48513529,56115373,54632123,63112099,29310653,40855196,28517837,60153475,31383920,65179854,50136281,53227366,31308546,8193332,45726101,52895238,27784424,26463724,1483660,54636082,35343140,24712611,57310928,17752123,20334826,52024546,10435522,10692567,62584932,67043017,5942211,33009438,35588580,14981298,9896951,11250308,11687432,60807806,34371954,50735401,30446090,48094479,13513070,55149664,6300180,37130779,23477051,12515670,1216481,32618462,44965884,27349320,65632624,43138527,59159939,49249512,55825640,29946664,19305861,54569503,420535,45345358,33062884,61038085,13656041,18007571,49218070,59585378,27842378,28654798,38070966,12853551,32856458,47352780,22745144,13757218,14139807,34375515,13913171,57366207,24791787,63525465,56067659,8025353,59045714,24678123,30707635,59306469,65407940,5866644,29383039,12785379,41534968,49923806,44532272,47231583,58593494,45083576,22747809,65874563,19314879,26765425,62782809,17754822,31060337,1446820,66296851,20922713,60523048,55169195,62863637,10964224,34171855,34672738,40772015,10360703,20452725,60099048,31363408,58218259,23726211,66622946,38665071,35561457,50878263,60249792,55096928,47476466,41506443,40992772,43975203,11199428,24777496,45880942,34186026,33495169,17365610,2294291,15501761,29082565,40005575,27562587,14751725,35896510,24688232,25682926,25703620,47823673,58836033,1323094,50930156,59396557,51869039,22185778,29698580,20398522,53016919,61409971,58607857,55504706,11425828,35668393,57982758,59828422,30758544,39532672,2343602,643491,4428721,59565512,30288194,4955924,36589781,51973850,19055412,1684500,63328579,8686390,45783606,12703261,13228685,24092578,15311999,42073758,48889127,23117366,57387574,28343464,43536901,28345035,47319592,18316080,24485504,62348324,31269066,62536834,27525043,21509110,63125756,7794997,33479941,34868664,59024951,28637366,20246655,57280701};
}
int main()
{
fastio;
int t = 1;
// cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}