QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#432189#8164. EX 中缀表达式Williamxzh16 1ms4156kbC++233.6kb2024-06-06 21:57:132024-06-06 21:57:14

Judging History

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

  • [2024-06-06 21:57:14]
  • 评测
  • 测评结果:16
  • 用时:1ms
  • 内存:4156kb
  • [2024-06-06 21:57:13]
  • 提交

answer

#include <bits/stdc++.h>
#define il inline
#define pii pair<int,int>
#define fi first
#define se second
#define RET {printf("error");exit(0);}
using namespace std;
typedef long long ll;
il ll qp(ll a,ll b,ll mod){
    ll ans=1ll;
    while(b){
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod,b>>=1;
    }return ans;
}
il ll getphi(ll x){
    ll ret=x,y,z;
    for(ll i=2;i*i<=x;++i){
        if(x%i) continue;
        while(x%i==0) x/=i;
        ret=(ret*(i-1ll))/i;
    }
    if(x>1) ret=(ret*(x-1ll))/x;
    return ret;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
il bool isch(char c){return (c>='0' && c<='9') || c=='.' || c=='+' || c=='*' || c=='^' || c=='(' || c==')';}
il bool isop(char c){return c=='.' || c=='+' || c=='*' || c=='^';}
il void cmin(int &x,int y){x=x<y?x:y;}
il void cmax(int &x,int y){x=x>y?x:y;}
const int N=10005,M=15;const ll mod=998244353;
int n,m,k,to[N];char s[N],op[M];ll mo[N];
il void init(){
    mo[0]=mod;
    for(int i=1;;++i){
        mo[i]=getphi(mo[i-1]);
        if(mo[i]==1){k=i;break;}
    }
    for(int i=k+1;i<N;++i) mo[i]=1;
}
struct NUM{
    int l,r,p;ll v;//t=0:a number, t=1: otherwise     p:which mo[p] this number shall mod      c:type in [1,m]
    il NUM(){l=r=p=0,v=0ll;}
    il NUM(int l,int r) : l(l),r(r) {}
};
struct OP{
    int l,r,c;
    il OP(){l=r=c=0;}
    il OP(int l,int r) : l(l),r(r) {}
};
int fa[N];pii c[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
il void Union(int x,int y){
    x=find(x),y=find(y);if(x==y) return ;
    fa[y]=x,cmin(c[x].fi,c[y].fi),cmax(c[x].se,c[y].se);
}
il ll solve(int l,int r,int cur){
    if(l>r) return -1;
    if(s[l]=='(' && s[r]==')' && to[l]==r) return solve(l+1,r-1,cur);
    int len,x,y,z,p,q,pre;ll u,v,w;
    vector<NUM> e;vector<OP> f;e.clear(),f.clear();
    x=l,pre=-1;
    for(int i=l;i<=r;++i){
        if(s[i]=='('){
            if(pre==0) return -1;
            e.push_back({i,to[i]});
            i=to[i],pre=0;continue;
        }
        if(!isdigit(s[i])) return -1;
        x=i;
        while(x<r && isdigit(s[x+1])) ++x;
        if(x>=r || !isop(s[x+1])) return -1;
        if(s[x+1]=='.') p=0,e.push_back({i,x+1});
        else if(isop(s[x+1])) p=1,f.push_back({i,x+1});
        else return -1;
        i=x+1;if(pre==p) return -1;
        pre=p;
    }
    for(int i=0;i<f.size();++i){
        if(f[i].r!=f[i].l+1 && s[f[i].l]!='0') return -1;
        f[i].c=s[f[i].r-1]-'0';
        if(!f[i].c) return -1;
    }
    if(f.size()!=e.size()-1) return -1;
    if(e.size()==1){
        u=0ll;
        for(int i=e[0].l;i<e[0].r;++i) u=(u*10ll+s[i]-'0')%mo[cur];
        return u;
    }
    for(int i=0;i<f.size();++i) f[i].c=s[f[i].l]-'0';
    len=e.size();
    for(int i=0;i<e.size();++i) e[i].p=cur,fa[i+1]=i+1,c[i]={i+1,i+1};
    //按优先级从小到大的合并,倒退出该模什么
    for(int j=1;j<=m;++j){
        for(int i=0;i<len-1;++i){
            if(f[i].c!=j) continue;
            x=i;while(x<len-2 && f[x+1].c==j) ++x;
            
        }
    }
    return 0ll;
}
ll ans;int st[N],top;
int main(){
    scanf("%d%s%s",&m,op+1,s+1);init();n=strlen(s+1);
    for(int i=1;i<=n;++i){
        if(s[i]=='(') st[++top]=i;
        else if(s[i]==')'){
            if(!top) RET
            to[i]=st[top],to[st[top]]=i,--top;
        }
    }
    ans=solve(1,n,0);
    if(ans==-1) RET
    else printf("%lld",ans);
    return 0;
}
/*
2
01
1.2+2.1^3.2*4.2^(5.2*6.)2+7.
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 24
25 26
27 28

((((002.001+003.)001*004.001+(((005.))))))

(002.001+003.)001*004.001+(((005.)))

(002.001+003.)001*004.001+(((005.)))
*/

詳細信息

Test #1:

score: 4
Accepted
time: 1ms
memory: 3728kb

input:

1
1
001.0+001.

output:

error

result:

ok single line: 'error'

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 3800kb

input:

1
1
002.001+003.001*004.001+005.

output:

0

result:

wrong answer 1st lines differ - expected: '29', found: '0'

Test #3:

score: 4
Accepted
time: 1ms
memory: 3728kb

input:

1
1
(1.)()

output:

error

result:

ok single line: 'error'

Test #4:

score: 0
Wrong Answer
time: 0ms
memory: 4104kb

input:

1
1
((((002.001+003.)001*004.001+(((005.))))))

output:

0

result:

wrong answer 1st lines differ - expected: '45', found: '0'

Test #5:

score: 4
Accepted
time: 1ms
memory: 3724kb

input:

1
1
1

output:

error

result:

ok single line: 'error'

Test #6:

score: 0
Wrong Answer
time: 1ms
memory: 3804kb

input:

1
0
000.001^000.001^001737356566464562245456526656565575.001^005985558448484954556451.

output:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'

Test #7:

score: 0
Wrong Answer
time: 0ms
memory: 3760kb

input:

1
0
005656646456224545652665.001^00848495.001^00173736565575.001^005985558444556451.

output:

0

result:

wrong answer 1st lines differ - expected: '707709398', found: '0'

Test #8:

score: 0
Wrong Answer
time: 1ms
memory: 3796kb

input:

1
1
001737356566464562245456526656565575.001^005985558448484954556451.001^000.001^000.

output:

0

result:

wrong answer 1st lines differ - expected: '64025176', found: '0'

Test #9:

score: 0
Wrong Answer
time: 1ms
memory: 3832kb

input:

1
1
0017373575.001^005985558448484954556451.001^0054565266565.001^00656646456224655.

output:

0

result:

wrong answer 1st lines differ - expected: '563281323', found: '0'

Test #10:

score: 4
Accepted
time: 1ms
memory: 3768kb

input:

1
1
((((1^))))

output:

error

result:

ok single line: 'error'

Test #11:

score: 0
Wrong Answer
time: 1ms
memory: 3808kb

input:

1
1
((((((((((((2.1^02.))01^3.01^02.))01^((03.01^03.))1^03.1^3.))01^((((02.1^3.))1^2.01^03.))01^((03.01^2.))1^02.1^03.))01^((((((3.01^02.))01^03.1^02.))1^((3.1^2.))1^2.1^03.))01^((((2.01^03.))01^2.01^2.))01^((02.1^2.))1^02.01^2.))1^((((((((2.1^2.))01^03.1^3.))1^((3.1^00.))1^2.1^2.))01^((((3.01^02.))...

output:

0

result:

wrong answer 1st lines differ - expected: '393739719', found: '0'

Test #12:

score: 0
Wrong Answer
time: 1ms
memory: 4096kb

input:

1
1
((((((((((((3.1^02.))1^03.1^03.))1^((1.1^3.))1^02.01^02.))01^((((2.01^1.))01^03.1^2.))1^((02.01^03.))01^03.1^02.))1^((((((02.1^03.))1^02.1^3.))01^((02.01^2.))01^2.1^02.))01^((((03.01^3.))1^3.1^3.))1^((3.1^02.))01^3.01^03.))01^((((((((01.1^2.))1^2.1^02.))01^((02.01^2.))01^3.1^3.))01^((((3.01^02.)...

output:

0

result:

wrong answer 1st lines differ - expected: '206923682', found: '0'

Test #13:

score: 0
Wrong Answer
time: 1ms
memory: 4084kb

input:

1
0
02.1^02.1^((3.01^02.))01^((3.01^01.1^((3.01^02.))))1^((3.01^02.01^((3.01^3.))01^((03.1^02.1^((2.1^03.))))))1^((03.1^02.1^((03.01^00.))1^((01.01^3.1^((2.01^02.))))01^((1.01^03.1^((02.1^02.))01^((03.01^03.01^((0.01^2.))))))))1^((03.01^03.1^((3.1^02.))01^((2.01^2.1^((3.01^01.))))01^((2.1^02.1^((2.1...

output:

0

result:

wrong answer 1st lines differ - expected: '336183747', found: '0'

Test #14:

score: 0
Wrong Answer
time: 1ms
memory: 3788kb

input:

1
1
((((((((((((03.1^02.))01^03.1^3.))1^((3.1^03.))01^3.1^02.))1^((((2.1^02.))01^2.01^2.))1^((03.1^03.))1^2.01^0.))01^((((((02.01^2.))01^2.1^2.))01^((03.1^2.))01^3.1^02.))1^((((03.1^03.))01^02.1^3.))01^((02.1^03.))1^03.1^03.))1^((((((((03.1^02.))1^2.1^02.))01^((03.01^2.))01^03.1^03.))1^((((2.01^2.))...

output:

0

result:

wrong answer 1st lines differ - expected: '737081821', found: '0'

Test #15:

score: 0
Wrong Answer
time: 0ms
memory: 3832kb

input:

1
0
1.1^2.1^((2.01^02.))1^((2.01^02.01^((2.1^02.))))01^((03.01^2.01^((3.01^02.))01^((02.1^03.1^((3.01^02.))))))01^((03.01^02.1^((01.1^03.))01^((2.01^3.01^((3.1^03.))))1^((03.01^2.1^((03.01^3.))1^((2.01^2.01^((03.1^2.))))))))01^((2.01^02.01^((03.01^03.))1^((3.1^3.1^((03.01^03.))))01^((3.01^3.01^((03....

output:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'

Test #16:

score: 0
Wrong Answer
time: 0ms
memory: 3768kb

input:

9
100011111
((((((((3.03*02.))9^3.09*03.4+((02.3+2.01*03.3+2.))2^((03.3^3.1+03.1+3.))8+((2.09*03.3+((02.03*3.))))))08*((((((3.04^03.))09*((02.2+03.))01+((3.4+03.))9*((3.7*03.))))6*((03.08^03.6*02.06^2.5*((01.05+2.03^03.09+02.))))))))08+((((03.5*2.02^03.06^2.01*2.09+03.6+((2.3^2.))))8^((((3.5^02.))6*...

output:

0

result:

wrong answer 1st lines differ - expected: '203844826', found: '0'

Test #17:

score: 0
Wrong Answer
time: 1ms
memory: 3936kb

input:

9
010010100
((((((((((02.06*2.03^((02.2+3.))))09^((((03.2^03.))03+02.05+03.))1+((02.08^00.3*2.4+03.1^((03.6^2.))9^((3.1+02.))))))9^((((((03.3+03.03*((03.1+01.))))7^((02.03^03.))09+((02.09+03.))))09*((((03.7^1.4+02.05+2.))9*((02.06*2.5*((03.03^3.))))))))03*((((((02.4+03.))7+((2.06^3.))))7^((01.01*02....

output:

0

result:

wrong answer 1st lines differ - expected: '473638651', found: '0'

Test #18:

score: 0
Wrong Answer
time: 1ms
memory: 3844kb

input:

9
111101110
((((((((((((2.2*03.))03*3.03+2.))08+((((02.07^02.))07+((3.04*02.))))07+((((2.1+3.))8+3.8+03.1^((03.01+03.))06*((03.3+02.))))1*((2.4+02.3+2.9+2.))08+((3.3*03.))9*((2.02^02.))7+((((02.02*3.))06^02.7^01.))07+((((2.01^02.))2+01.8+03.))))3*((((((3.5+2.))08^((02.6+03.))02^3.07^3.5^03.6^2.))3+(...

output:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'

Test #19:

score: 0
Wrong Answer
time: 1ms
memory: 4156kb

input:

9
111011011
((((((((3.08*2.07*((02.1*3.))07+((3.2*02.01^3.8^2.))))8^((((2.09*3.2^03.04+02.))4+((03.06*02.4+((00.01*02.))))))))8^((((3.06^2.))09^03.9^02.03^((0.4+03.02*2.05^00.))))9^((((03.1^02.))6+((02.01^3.))01+((02.03*02.))07+2.9+2.))01*((((02.6*02.4*02.8*2.))6*((03.2^02.))09^((3.7+2.))))08+((((03...

output:

0

result:

wrong answer 1st lines differ - expected: '788040634', found: '0'

Test #20:

score: 0
Wrong Answer
time: 1ms
memory: 3796kb

input:

9
100110101
((((((((3.5*3.))7^((2.3+3.))05+2.8^2.05^3.8*2.))7^03.08*02.8^((2.7+00.))08*((2.2^2.))09+((2.7*2.))06+((((((03.08*3.1*02.4+03.))1+02.03*2.2^3.05*02.))01*((2.7+02.01+02.02+02.))9*((03.02+03.1^0.03^3.))))05*((((((((02.01*02.))5*03.06+3.))5+((2.04*2.1*3.1+02.))02^((((03.7*03.01+2.01^3.))1+2....

output:

0

result:

wrong answer 1st lines differ - expected: '151078698', found: '0'

Test #21:

score: 0
Wrong Answer
time: 1ms
memory: 3868kb

input:

9
010011011
((((((((3.5^3.4+02.06+02.))09*((2.05^03.01*2.6*02.))03^((2.07+02.5*((03.04^0.))01+((02.4+03.))07+2.09^03.))))06+((((((02.1^2.))03^2.06^3.))7^((((2.01*02.))6*03.9*2.))04+((((3.05+2.01+3.7+2.))02+3.04*02.4^03.7+2.))))05+((((((02.07+3.))9+((3.08*2.))5*((2.8+02.02^((3.01*02.))))))08*((((02.0...

output:

0

result:

wrong answer 1st lines differ - expected: '926442773', found: '0'

Test #22:

score: 0
Wrong Answer
time: 1ms
memory: 3828kb

input:

9
010111110
((((((((2.09+2.7*((3.03^03.))02^((03.01*03.))3*03.6^03.))04+((((02.03*3.))06+((3.01^02.))))9*((((03.4*3.))09^((03.1+2.))))))06*((03.7+02.06^((2.5*03.))1+((00.09+3.1*2.9+2.))))7+((03.8^02.3^2.06^3.))08^((3.8^02.04+3.7*03.))04^((((2.07+3.5^((02.01^03.))))05*((03.01+03.))7^3.09^3.))09^((((2...

output:

0

result:

wrong answer 1st lines differ - expected: '482698727', found: '0'

Test #23:

score: 0
Wrong Answer
time: 0ms
memory: 3852kb

input:

9
101011110
((((((((3.9+01.09^((03.6^03.))05+((2.06^3.03+((00.1*03.))))))8^((02.6+02.02*03.6*02.02^((2.07+02.))7+((3.04+02.))))1*((((02.06+03.))8+((2.7+0.))01*((02.3*3.))9^((02.1^2.))))8^((((2.6^02.))8^((3.1+0.))7*((02.6*02.))8*((3.07+2.))))))05*((((03.4^2.03^((03.2*02.))))05*2.07+03.6+3.06+2.1^((2....

output:

0

result:

wrong answer 1st lines differ - expected: '665120433', found: '0'

Test #24:

score: 0
Wrong Answer
time: 1ms
memory: 4140kb

input:

9
101010100
((((((((((03.08+02.03+2.9^2.))9^((2.9+3.04+((02.2*02.))))2^((2.05+3.))6+3.7^2.3^2.7+03.3+3.9*3.))09*((((3.9*3.7*3.7*3.))9^((((03.04+03.))07^2.08*1.))3*03.8+02.04+((02.4+2.))04+((2.5+02.))6*((02.01+3.))))4*((((03.04+2.))08*((03.07^03.))03^2.07*3.05^((3.04*02.))2+((03.5^3.3*((03.2*3.))))03...

output:

0

result:

wrong answer 1st lines differ - expected: '487727059', found: '0'

Test #25:

score: 0
Wrong Answer
time: 1ms
memory: 3768kb

input:

9
010000001
((((((((2.05^03.4+((03.02^2.))))06^((((2.3+03.))06+((2.06*03.))))))8^((((((02.04^03.))07^((2.7+03.))))08+((3.06+03.))9^((2.02^3.))))3*((2.05^2.01^2.09^03.))07*((2.6*2.2+3.6+2.))04+((((02.05*2.02^02.02+02.))02^2.07^3.06+((3.6+3.))))01^((((((((2.01^02.))2^2.07^03.))8*((03.6*3.6^02.09^3.)))...

output:

0

result:

wrong answer 1st lines differ - expected: '529906102', found: '0'