結果
問題 | No.5005 3-SAT |
ユーザー |
![]() |
提出日時 | 2022-04-29 14:38:48 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 2,125 bytes |
コンパイル時間 | 2,478 ms |
実行使用メモリ | 6,956 KB |
スコア | 32,160 |
最終ジャッジ日時 | 2022-04-29 14:38:55 |
合計ジャッジ時間 | 7,542 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/twosat> using namespace std; using ll = long long; template <class T, class F> 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] = {}; for (int j = 0; j < M; j++) { r[j] = -1; } auto s = UpperBound<int>(1, N + 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]); } return ts.satisfiable(); }) - 1; 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]); } ts.satisfiable(); auto v = ts.answer(); for (int j = 0; j < M; j++) { r[j] = v[j]; } for (int j = M - 1; j >= 0; j--) { if (r[j] < 0) r[j] = 0; } 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; }