QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#402201 | #1081. Satisfaction Guaranteed | stasio6# | RE | 0ms | 0kb | C++14 | 4.0kb | 2024-04-30 07:27:51 | 2024-04-30 07:27:52 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
typedef pair<int, int> pii;
typedef vector<int> vi;
template<class X, class Y> X cmx(X &a, Y b) { a = max<X>(a, b); }
#define ary(k) array<int, k>
int b[26],f[26];
vector <int> oth;
int slv(string &s,int l,int r){
int tot=0;
for(int i=l,now=-1;i<=r;i++){
if(s[i]=='|'){
assert(now!=-1);
tot|=now;
now=-1;
}
else if(s[i]=='&'){
assert(now!=-1);
assert(s[i+1]>='A'&&s[i+1]<='Z'||s[i+1]=='('||s[i+1]=='~');
int fff=0;
if(s[i+1]=='~') i++,fff=1;
if(s[i+1]=='('){
now&=slv(s,i+2,oth[i+1]-1)^fff;
i=oth[i+1];
}
else now&=b[f[s[i+1]-'A']]^fff,i++;
}
else{
assert(s[i]>='A'&&s[i]<='Z'||s[i]=='~'||s[i]=='(');
int fff=0;
if(s[i]=='~') i++,fff=1;
if(s[i]=='('){
now=slv(s,i+1,oth[i]-1)^fff;
i=oth[i];
}
else now=b[f[s[i]-'A']]^fff;
}
}
}
void solve(vector <string> v,vector <string> bl){
int now=0;
while(1) {
if (v[now] == "if") {
string exp, useless;
now++,exp=v[now];
now++;
vector <string> oper;
while (v[now] != "fi"&&v[now]!="else") oper.push_back(v[now++]);
bl.push_back(exp);
solve(oper,bl);
bl.pop_back();
now++;
if(v[now-1]=="else"){
oper.clear();
while(v[now]!="fi") oper.push_back(v[now++]);
exp.push_back('?');
bl.push_back(exp);
solve(oper,bl);
bl.pop_back();
now++;
}
}
else{
assert(v[now]=="checkpoint");
int cnt=0,ch[26];
memset(f,0,sizeof(f));
for(auto s:bl){
for(auto x:s){
if(x>='A'&&x<='Z'){
if(!f[x-'A']) f[x-'A']=++cnt,ch[cnt]=x-'A';
}
}
}
sort(ch,ch+26);
for(int i=1;i<=cnt;i++) f[ch[i]]=i;
int valid[26][2];
for(int i=1;i<=cnt;i++) valid[i][0]=valid[i][1]=0;
for(int i=0;i<(1<<cnt);i++){
for(int j=1;j<=cnt;j++) b[j]=((1<<(j-1))&i)>1;
int flag=0;
for(auto s:bl){
int fuck=0;
if(s.back()=='?') fuck=-1,s.pop_back();
vector <int> st;
oth.resize(s.size());
for(int i=0;i<s.size();i++){
if(s[i]=='(') st.push_back(i);
else if(s[i]==')'){
oth[i]=st.back();
oth[st.back()]=i;
st.pop_back();
}
}
flag&=slv(s,0,s.size()-1)^fuck;
}
if(flag){
for(int j=1;j<=cnt;j++) valid[j][b[j]]=1;
}
}
int hass=0;
string ans="";
for(int i=1;i<=cnt;i++){
hass+=valid[i][0]+valid[i][1];
if(valid[i][0]&&!valid[i][1]) ans+='a'+ch[i];
if(valid[i][1]&&!valid[i][0]) ans+='A'+ch[i];
}
if(hass==0) cout<<">unreachable\n";
else cout<<'>'<<ans<<'\n';
now++;
}
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
string s;
vector <string> v,bl;
while(cin>>s) v.push_back(s);
solve(v,bl);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
if X then checkpoint if ~X then checkpoint fi else checkpoint fi if X|~X then checkpoint fi if Y then if ~X then checkpoint fi fi if ~~~~X then checkpoint fi if ~~~~~X then checkpoint fi if (((((X))))) then checkpoint fi if ((~((~~~((X)))))) then checkpoint fi if X&Y|Z ...