QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #655091 | #8164. EX 中缀表达式 | Hadtsti | 60 | 1ms | 3968kb | C++14 | 2.0kb | 2024-10-19 00:28:04 | 2024-10-19 00:28:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int M[30]={998244353,998244352,402653184,134217728,67108864,33554432,16777216,8388608,4194304,2097152,1048576,524288,262144,131072,65536,32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2};
int n,m,mc[10010],stk[10010],tp;
bool fg[10];
char str[10010];
struct node
{
int v;
bool c;
};
inline int mod(int x)
{
return x>29?1:M[x];
}
inline node pw(int a,int b,int m)
{
int res=1;
bool FG=0;
for(;b;b>>=1)
{
if(b&1)
res=1ll*res*a%m,FG|=(1ll*res*a>=mod(0));
a=1ll*a*a%m;
}
return {res,FG};
}
node calc(int l,int r,int c)
{
if(mc[l]==r)
return calc(l+1,r-1,c);
int pos=l;
bool Fg=1;
tp=0;
while(pos<=r)
{
Fg^=1;
if(mc[pos])
{
pos=mc[pos]+1;
continue;
}
if(Fg)
{
while(str[pos]=='0')
pos++;
while(tp&&str[stk[tp]]>str[pos])
tp--;
stk[++tp]=pos;
pos++;
}
else
while(str[pos]!='.')
pos++;
pos++;
}
if(!tp)
{
node res={0,0};
int Pos=r;
for(int i=l;i<r;i++)
{
if(Pos==r&&str[i]-'0')
Pos=i;
res.v=(10ll*res.v+str[i]-'0')%mod(c);
}
if(r-Pos>9)
res.c=1;
return res;
}
int mid=stk[1],col=str[mid];
if(!fg[str[mid]-'0'])
for(int i=2;i<=tp&&str[stk[i]]==col;i++)
mid=stk[i];
int tmid=mid-1;
while(str[tmid]=='0')
tmid--;
node a=calc(l,tmid,c),b=calc(mid+2,r,c+(str[mid+1]=='^')),res={0,0};
res.c=a.c|b.c;
if(str[mid+1]=='+')
{
res.c|=(a.v+b.v>=mod(0));
res.v=(a.v+b.v)%mod(c);
}
else if(str[mid+1]=='*')
{
res.c|=(1ll*a.v*b.v>=mod(0));
res.v=1ll*a.v*b.v%mod(c);
}
else
res=pw(a.v,b.v+(b.c?mod(c+1):0),mod(c));
return res;
}
int main()
{
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%1d",&fg[i]);
scanf("%s",str+1);
n=strlen(str+1);
for(int i=1;i<=n;i++)
{
if(str[i]==')')
{
if(!tp)
{
puts("error");
return 0;
}
mc[stk[tp--]]=i;
}
if(str[i]=='(')
stk[++tp]=i;
}
printf("%d",calc(1,n,0).v);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3872kb
input:
1 1 001.0+001.
output:
1
result:
wrong answer 1st lines differ - expected: 'error', found: '1'
Test #2:
score: 4
Accepted
time: 0ms
memory: 3800kb
input:
1 1 002.001+003.001*004.001+005.
output:
29
result:
ok single line: '29'
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 3788kb
input:
1 1 (1.)()
output:
-79278
result:
wrong answer 1st lines differ - expected: 'error', found: '-79278'
Test #4:
score: 4
Accepted
time: 0ms
memory: 3680kb
input:
1 1 ((((002.001+003.)001*004.001+(((005.))))))
output:
45
result:
ok single line: '45'
Test #5:
score: 0
Runtime Error
input:
1 1 1
output:
result:
Test #6:
score: 4
Accepted
time: 0ms
memory: 3680kb
input:
1 0 000.001^000.001^001737356566464562245456526656565575.001^005985558448484954556451.
output:
1
result:
ok single line: '1'
Test #7:
score: 4
Accepted
time: 0ms
memory: 3932kb
input:
1 0 005656646456224545652665.001^00848495.001^00173736565575.001^005985558444556451.
output:
707709398
result:
ok single line: '707709398'
Test #8:
score: 4
Accepted
time: 0ms
memory: 3728kb
input:
1 1 001737356566464562245456526656565575.001^005985558448484954556451.001^000.001^000.
output:
64025176
result:
ok single line: '64025176'
Test #9:
score: 4
Accepted
time: 1ms
memory: 3880kb
input:
1 1 0017373575.001^005985558448484954556451.001^0054565266565.001^00656646456224655.
output:
563281323
result:
ok single line: '563281323'
Test #10:
score: 0
Runtime Error
input:
1 1 ((((1^))))
output:
result:
Test #11:
score: 4
Accepted
time: 0ms
memory: 3812kb
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:
393739719
result:
ok single line: '393739719'
Test #12:
score: 0
Wrong Answer
time: 0ms
memory: 3740kb
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:
737081821
result:
wrong answer 1st lines differ - expected: '206923682', found: '737081821'
Test #13:
score: 0
Wrong Answer
time: 0ms
memory: 3872kb
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:
489538247
result:
wrong answer 1st lines differ - expected: '336183747', found: '489538247'
Test #14:
score: 4
Accepted
time: 0ms
memory: 3808kb
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:
737081821
result:
ok single line: '737081821'
Test #15:
score: 4
Accepted
time: 1ms
memory: 3820kb
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:
1
result:
ok single line: '1'
Test #16:
score: 0
Wrong Answer
time: 1ms
memory: 3900kb
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:
926096382
result:
wrong answer 1st lines differ - expected: '203844826', found: '926096382'
Test #17:
score: 4
Accepted
time: 1ms
memory: 3904kb
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:
473638651
result:
ok single line: '473638651'
Test #18:
score: 4
Accepted
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:
1
result:
ok single line: '1'
Test #19:
score: 0
Wrong Answer
time: 1ms
memory: 3968kb
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:
789456392
result:
wrong answer 1st lines differ - expected: '788040634', found: '789456392'
Test #20:
score: 4
Accepted
time: 0ms
memory: 3968kb
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:
151078698
result:
ok single line: '151078698'
Test #21:
score: 0
Wrong Answer
time: 1ms
memory: 3916kb
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:
486852288
result:
wrong answer 1st lines differ - expected: '926442773', found: '486852288'
Test #22:
score: 4
Accepted
time: 1ms
memory: 3908kb
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:
482698727
result:
ok single line: '482698727'
Test #23:
score: 0
Wrong Answer
time: 0ms
memory: 3840kb
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:
949512240
result:
wrong answer 1st lines differ - expected: '665120433', found: '949512240'
Test #24:
score: 4
Accepted
time: 1ms
memory: 3716kb
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:
487727059
result:
ok single line: '487727059'
Test #25:
score: 4
Accepted
time: 1ms
memory: 3892kb
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:
529906102
result:
ok single line: '529906102'