#include #include using namespace std; using ll = long long; template T UpperBound(T i0, T i1, F f) { while (i0 < i1) { T i = i0 + (i1 - i0) / 2; if (f(i)) i0 = i + 1; else i1 = i; } return i0; } constexpr int N = 2048, M = 256, K = 1; int a[N][6]; int main() { mt19937_64 rnd; int sc = 0; for (int k = 0; k < K; k++) { for (int i = 0; i < N; i++) { for (int h = 0; h < 6; h++) { if (K == 1) { cin >> a[i][h]; } else { a[i][h] = rnd() % (h < 3 ? 256 : 2); } } } int r[M] = {}; vector v; int s = UpperBound(1, 500 + 1, [&](auto s) { atcoder::two_sat ts(M); for (int i = 0; i < s; i++) { ts.add_clause(a[i][0], a[i][3], a[i][1], a[i][4]); } int b = ts.satisfiable(); if (b) v = ts.answer(); return b; }) - 1; for (int l = 0; l < 10000; l++) { int s0 = s; atcoder::two_sat ts(M); for (int i = 0; i < s; i++) { ts.add_clause(a[i][0], a[i][3], a[i][1], a[i][4]); } for (int i = s; i < N; i++) { ts.add_clause(a[i][0], a[i][3], a[i][1], a[i][4]); int b = ts.satisfiable(); if (b) v = ts.answer(), s = i + 1; else break; } if (s == s0) { for (int i = 0; i < s + 1; i++) { int h0 = 2, h1 = rnd() % 2; swap(a[i][h0], a[i][h1]); swap(a[i][h0 + 3], a[i][h1 + 3]); } } else { swap(a[s][rnd() % 2], a[s][2]); } } for (int l = 0; l < 100000; l++) { int x[M] = {}; for (int i = 0; i < s; i++) { int c = 0; for (int h = 0; h < 3; h++) { c += r[a[i][h]] == a[i][h + 3]; } if (c == 1) { for (int h = 0; h < 3; h++) { if (r[a[i][h]] == a[i][h + 3]) { x[a[i][h]]++; break; } } } } int b = 0; for (int h = 0; h < 3; h++) { if (x[a[s][h]] == 0) { r[a[s][h]] = a[s][h + 3]; s++; b = 1; break; } } if (b == 0) { for (int i = 0; i < s; i++) { int c = 0; for (int h = 0; h < 3; h++) { c += r[a[i][h]] == a[i][h + 3]; } if (c > 1) { int h1 = rnd() % 3; for (int h0 = 0; h0 < 3; h0++) { int h = (h0 + h1) % 3; if (x[a[i][h]] == 0) r[a[i][h]] ^= 1; } break; } } } } for (int j = 0; j < M; j++) { r[j] = v[j]; } if (K == 1) { for (int j = M - 1; j >= 0; j--) { cout << r[j]; } cout << endl; } else { int s = N; for (int i = 0; i < N; i++) { int b = 0; for (int h = 0; h < 3; h++) { if (r[a[i][h]] == a[i][h + 3]) { b = 1; break; } } if (b == 0) { s = i; break; } } cout << s << '\n'; sc += s; } } if (K > 1) { cout << sc * 100 / K << '\n'; } return 0; }