| 29 | } else if (!assume(cl[t])) return false; } |
| 30 | return true; } |
| 31 | bool bt() { |
| 32 | int v = log.size(), x; ll b = -1; |
| 33 | rep(i,0,n) if (val[2*i] == val[2*i+1]) { |
| 34 | ll s = 0, t = 0; |
| 35 | rep(j,0,2) { iter(it,loc[2*i+j]) |
| 36 | s+=1LL<<max(0,40-tail[*it]+head[*it]); swap(s,t); } |
| 37 | if (max(s,t) >= b) b = max(s,t), x = 2*i + (t>=s); } |
| 38 | if (b == -1 || (assume(x) && bt())) return true; |
| 39 | while (log.size() != v) { |
| 40 | int p = log.back().first, q = log.back().second; |
| 41 | if (p == -1) val[q] = false; else head[p] = q; |
| 42 | log.pop_back(); } |
| 43 | return assume(x^1) && bt(); } |
| 44 | bool solve() { |
| 45 | val.assign(2*n+1, false); |
| 46 | w.assign(2*n+1, vi()); loc.assign(2*n+1, vi()); |