#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #include #include class Randomizer_NV{ public: using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; private: u32 rngx = 1234567890; u32 rngy = 987654321; u32 rngz = 998244353; u32 rngw = 1000000007; public: void seed(u32 x = 1234567890, u32 y = 987654321, u32 z = 998244353, u32 w = 1000000007){ rngx = x; rngy = y; rngz = z; rngw = w; } u32 rng32() { const u32 t = rngx ^ (rngx << 11); rngx = rngy; rngy = rngz; rngz = rngw; return rngw = rngw ^ (rngw >> 19) ^ t ^ (t >> 8); } }; #include #include #include #include #include #include using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) using m32 = atcoder::static_modint<998244353>; const int N = 2048; const int BIT_SIZE = 256; int TARGET = 700; struct Constraint{ pair a[3]; }; Randomizer_NV rng; int A[N][3][2] = {}; int edges[N*6] = {}; int edges_i[N+1] = {}; int final_score = -1; int ans[BIT_SIZE] = {}; int final_ans[BIT_SIZE] = {}; const int N_BITSET = 32; u64 satisfied[N_BITSET] = {}; int calc_score(int* ans){ rep(i,N){ bool ok = false; rep(t,3) if(ans[A[i][t][0]] == A[i][t][1]){ ok = true; break; } if(!ok) return i; } return N; } void update_satisfied(int* ans, int p){ for(int ei=edges_i[p]; ei> A[i][t][c]; rep(i,N) rep(t,3) A[i][t][0] = BIT_SIZE - 1 - A[i][t][0]; rep(i,N_BITSET) satisfied[i] = 0; for(int i=0; i<=BIT_SIZE; i++) edges_i[i] = 0; rep(i,1200) rep(t,3) edges_i[A[i][t][0]]++; rep(i,BIT_SIZE) edges_i[i+1] += edges_i[i]; rep(i,1200) rep(t,3) edges[--edges_i[A[i][t][0]]] = i; int attempts = 0; const int TIME_SPLIT_COUNT = 10; rep(time_split, TIME_SPLIT_COUNT){ rep(i,BIT_SIZE) ans[i] = rng.rng32() % 2; initialize_satisfied(ans); int pscore = calc_score2(); while(true){ auto end_time = chrono::high_resolution_clock::now(); if((end_time - start_time).count() >= 1'000'000'000 * 1.8 / TIME_SPLIT_COUNT * (time_split + 1)) break; rep(t,1000){ attempts++; int p = rng.rng32() & 255; ans[p] ^= 1; update_satisfied(ans, p); int score = calc_score2(); if(final_score < score){ rep(i,BIT_SIZE) final_ans[i] = ans[i]; final_score = score; } if(pscore > score){ ans[p] ^= 1; update_satisfied(ans, p); } else pscore = score; } } } rep(i,BIT_SIZE) if(final_ans[i] == -1) final_ans[i] = 0; rep(i,BIT_SIZE) cout << final_ans[i]; final_score = calc_score(final_ans); cerr << "Final Score = " << final_score << endl; cout << endl; cerr << "attempts = " << attempts << endl; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } ios_do_not_sync_instance;