#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; ll g_start_cycle; const ll CYCLE_PER_SEC = 2400000000; double TIME_LIMIT = 1.8; unsigned long long int get_cycle() { unsigned int low, high; __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high)); return ((unsigned long long int) low) | ((unsigned long long int) high << 32); } double get_time(unsigned long long int begin_cycle) { return (double) (get_cycle() - begin_cycle) / CYCLE_PER_SEC; } unsigned long long xor128() { static unsigned long long rx = 123456789, ry = 362436069, rz = 521288629, rw = 88675123; unsigned long long rt = (rx ^ (rx << 11)); rx = ry; ry = rz; rz = rw; return (rw = (rw ^ (rw >> 19)) ^ (rt ^ (rt >> 8))); } const int QUERY_NUM = 2048; const int L = 256; const int BIT_PTN[8][3] = { {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 1, 1}, {1, 0, 0}, {1, 0, 1}, {1, 1, 0}, {1, 1, 1}, }; struct Query { int a; int b; int c; int p; int q; int r; Query(int a = -1, int b = -1, int c = -1, int p = -1, int q = -1, int r = -1) { this->a = a; this->b = b; this->c = c; this->p = p; this->q = q; this->r = r; } }; vector g_query_list; vector g_ids[QUERY_NUM]; int g_bit_ptn[L]; class SAT { public: void init() { g_start_cycle = get_cycle(); setup(); } void setup() { vector G[L]; for (int i = 0; i < QUERY_NUM; ++i) { Query &query = g_query_list[i]; G[query.a].push_back(i); G[query.b].push_back(i); G[query.c].push_back(i); } for (int i = 0; i < QUERY_NUM; ++i) { Query &query = g_query_list[i]; set ids; for (int id : G[query.a]) { ids.insert(id); } for (int id : G[query.b]) { ids.insert(id); } for (int id : G[query.c]) { ids.insert(id); } for (int id : ids) { g_ids[i].push_back(id); } } } string run() { string res = ""; init(); search_best_bit_ptn(); return res; } vector search_best_bit_ptn() { memset(g_bit_ptn, 0, sizeof(g_bit_ptn)); int best_bit_ptn[L]; memcpy(best_bit_ptn, g_bit_ptn, sizeof(g_bit_ptn)); vector res(L, 0); int cur_score = calc_score_full(); int best_score = cur_score; double cur_time = get_time(g_start_cycle); int try_count = 0; double total_diff = 0.0; double t = 3.0; int R = 500000; while (cur_time < TIME_LIMIT) { cur_time = get_time(g_start_cycle); double remain_time = (TIME_LIMIT - cur_time) / TIME_LIMIT; int qid = cur_score; Query &q = g_query_list[qid]; int idx = xor128() % 3; flip(qid, idx); int score = calc_score_full(); double diff_score = score - cur_score; total_diff += fabs(diff_score); if (diff_score > 0 || (xor128() % R < R * exp(diff_score / (t * sqrt(remain_time))))) { cur_score = score; if (best_score < score) { best_score = score; memcpy(best_bit_ptn, g_bit_ptn, sizeof(g_bit_ptn)); } } else { flip(qid, idx); } ++try_count; double average_diff = total_diff / try_count; t = 0.5 * remain_time * average_diff; } memcpy(g_bit_ptn, best_bit_ptn, sizeof(best_bit_ptn)); int score = calc_score_full(); fprintf(stderr, "try_count: %d, best_score: %d\n", try_count, score); return res; } void flip(int qid, int idx) { Query &q = g_query_list[qid]; switch (idx) { case 0: g_bit_ptn[q.a] ^= 1; break; case 1: g_bit_ptn[q.b] ^= 1; break; case 2: g_bit_ptn[q.c] ^= 1; break; default: assert(false); } } int calc_score_full() { int score = 0; for (int qid = 0; qid < QUERY_NUM; ++qid) { Query &query = g_query_list[qid]; if (g_bit_ptn[query.a] == query.p || g_bit_ptn[query.b] == query.q || g_bit_ptn[query.c] == query.r) { ++score; } else { break; } } return score; } void search_best_ptn(int qid) { Query &q = g_query_list[qid]; int best_score = 0; int best_ptn_id = 0; for (int pid = 0; pid < 8; ++pid) { g_bit_ptn[q.a] = BIT_PTN[pid][0]; g_bit_ptn[q.b] = BIT_PTN[pid][1]; g_bit_ptn[q.c] = BIT_PTN[pid][2]; int score = 0; for (int id : g_ids[qid]) { Query &query = g_query_list[id]; if (g_bit_ptn[query.a] == query.p || g_bit_ptn[query.b] == query.q || g_bit_ptn[query.c] == query.r) { score++; } else { break; } } if (best_score < score) { best_score = score; best_ptn_id = pid; } } g_bit_ptn[q.a] = BIT_PTN[best_ptn_id][0]; g_bit_ptn[q.b] = BIT_PTN[best_ptn_id][1]; g_bit_ptn[q.c] = BIT_PTN[best_ptn_id][2]; } }; int main() { int a, b, c, p, q, r; for (int i = 0; i < QUERY_NUM; ++i) { cin >> a >> b >> c >> p >> q >> r; g_query_list.push_back(Query(a, b, c, p, q, r)); } SAT sat; sat.run(); string res = ""; for (int i = 0; i < L; ++i) { res += to_string(g_bit_ptn[i]); } reverse(res.begin(), res.end()); cout << res << endl; return 0; }