QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#402200#1081. Satisfaction Guaranteedstasio6#RE 0ms0kbC++144.0kb2024-04-30 07:26:302024-04-30 07:26:30

Judging History

你现在查看的是最新测评结果

  • [2024-04-30 07:26:30]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-04-30 07:26:30]
  • 提交

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';
        }

    }
}
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 ...

output:


result: