Submission #1556309
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define GET_MACRO(_1, _2, _3, NAME, ...) NAME #define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define _rep(i,n) _repl(i,0,n) #define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__) #define mp(a,b) make_pair((a),(b)) #define pb(a) push_back((a)) #define all(x) (x).begin(),(x).end() #define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x)) #define fi first #define se second #define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__) void _dbg(string){cout<<endl;} template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);} template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;} template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;} #define INF 1120000000 string s,t; vector<pair<int,int>> vec; int p=0; int literal(){ bool neg = false; if(s[p]=='~'){p++;neg=true;} int ret = 0; while(isdigit(s[p])){ ret = ret*10 + s[p++] - '0'; } if(neg) return -ret; else return ret; } void clause(){ assert(s[p++]=='('); int l = literal(); assert(s[p++]=='v'); int r = literal(); vec.pb(mp(l,r)); assert(s[p++]==')'); } void parse(){ clause(); while(p < s.size()){ assert(s[p++]=='^'); clause(); } } int ans = 11; void dfs(int d, vector<bool> bl){ bool ok = true; for(auto &pa : vec){ int l = pa.first, r = pa.second; bool val = false; if(l>0) val |= bl[l]; else val |= !bl[-l]; if(r>0) val |= bl[r]; else val |= !bl[-r]; if(!val){ ok = false; if(d<10){ bl[abs(l)] = !bl[abs(l)]; dfs(d+1, bl); bl[abs(l)] = !bl[abs(l)]; bl[abs(r)] = !bl[abs(r)]; dfs(d+1, bl); bl[abs(r)] = !bl[abs(r)]; } break; } } if(ok) ans = min(ans, d); } int main(){ int n,m; cin>>n>>m; cin>>s>>t; parse(); assert(m==vec.size()); vector<bool> bl(n+1); rep(i,n) bl[i+1] = t[i]=='T'; dfs(0,bl); if(ans>10) cout << "TOO LARGE" << endl; else cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - 2-SAT |
User | tossy |
Language | C++14 (GCC 5.4.1) |
Score | 200 |
Code Size | 2282 Byte |
Status | AC |
Exec Time | 274 ms |
Memory | 3332 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 200 / 200 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00-sample-00, 00-sample-10, 00-sample-20, 10-sat-00, 10-sat-01, 10-sat-02, 10-sat-03, 10-sat-04, 10-sat-05, 10-sat-06, 10-sat-07, 10-sat-08, 10-sat-09, 10-sat-10, 10-sat-11, 10-sat-12, 10-sat-13, 10-sat-14, 10-sat-15, 10-sat-16, 10-sat-17, 10-sat-18, 10-sat-19, 10-sat-20, 10-sat-21, 10-sat-22, 10-sat-23, 10-sat-24, 10-sat-25, 10-sat-26, 10-sat-27, 10-sat-28, 10-sat-29, 10-sat-30, 10-sat-31, 10-sat-32, 10-sat-33, 10-sat-34, 10-sat-35, 10-sat-36, 10-sat-37, 10-sat-38, 10-sat-39, 20-unsat-00, 20-unsat-01, 20-unsat-02, 20-unsat-03, 20-unsat-04, 20-unsat-05, 20-unsat-06, 20-unsat-07, 20-unsat-08, 20-unsat-09 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00-sample-00 | AC | 1 ms | 256 KB |
00-sample-10 | AC | 1 ms | 256 KB |
00-sample-20 | AC | 1 ms | 256 KB |
10-sat-00 | AC | 6 ms | 640 KB |
10-sat-01 | AC | 4 ms | 512 KB |
10-sat-02 | AC | 22 ms | 1540 KB |
10-sat-03 | AC | 10 ms | 776 KB |
10-sat-04 | AC | 67 ms | 2820 KB |
10-sat-05 | AC | 25 ms | 1156 KB |
10-sat-06 | AC | 153 ms | 3332 KB |
10-sat-07 | AC | 98 ms | 2052 KB |
10-sat-08 | AC | 231 ms | 3332 KB |
10-sat-09 | AC | 49 ms | 900 KB |
10-sat-10 | AC | 274 ms | 3332 KB |
10-sat-11 | AC | 139 ms | 1796 KB |
10-sat-12 | AC | 234 ms | 3332 KB |
10-sat-13 | AC | 222 ms | 3204 KB |
10-sat-14 | AC | 153 ms | 3332 KB |
10-sat-15 | AC | 31 ms | 900 KB |
10-sat-16 | AC | 88 ms | 3332 KB |
10-sat-17 | AC | 10 ms | 640 KB |
10-sat-18 | AC | 56 ms | 3332 KB |
10-sat-19 | AC | 45 ms | 2820 KB |
10-sat-20 | AC | 49 ms | 3332 KB |
10-sat-21 | AC | 10 ms | 900 KB |
10-sat-22 | AC | 46 ms | 3332 KB |
10-sat-23 | AC | 13 ms | 1028 KB |
10-sat-24 | AC | 47 ms | 3332 KB |
10-sat-25 | AC | 40 ms | 2948 KB |
10-sat-26 | AC | 47 ms | 3332 KB |
10-sat-27 | AC | 26 ms | 1796 KB |
10-sat-28 | AC | 47 ms | 3332 KB |
10-sat-29 | AC | 14 ms | 1028 KB |
10-sat-30 | AC | 47 ms | 3332 KB |
10-sat-31 | AC | 15 ms | 1156 KB |
10-sat-32 | AC | 47 ms | 3332 KB |
10-sat-33 | AC | 16 ms | 1156 KB |
10-sat-34 | AC | 47 ms | 3332 KB |
10-sat-35 | AC | 6 ms | 644 KB |
10-sat-36 | AC | 49 ms | 3332 KB |
10-sat-37 | AC | 6 ms | 640 KB |
10-sat-38 | AC | 47 ms | 3332 KB |
10-sat-39 | AC | 11 ms | 1028 KB |
20-unsat-00 | AC | 47 ms | 3332 KB |
20-unsat-01 | AC | 32 ms | 2564 KB |
20-unsat-02 | AC | 47 ms | 3332 KB |
20-unsat-03 | AC | 6 ms | 640 KB |
20-unsat-04 | AC | 47 ms | 3332 KB |
20-unsat-05 | AC | 8 ms | 644 KB |
20-unsat-06 | AC | 47 ms | 3332 KB |
20-unsat-07 | AC | 40 ms | 3076 KB |
20-unsat-08 | AC | 47 ms | 3332 KB |
20-unsat-09 | AC | 24 ms | 1796 KB |