提交记录 #24067

编号	题目	状态	分数	总时间	内存	代码 / 答案文件	提交者	提交时间
#24067	#1137. JM的算术表达式（3）	Wrong Answer	45	76 ms	428 K	C++ 11 / 4.2 K	pcw0118	2020-03-18 17:50:10

显示原始代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>

using namespace std;

#define ll long long
const int MAX = 1e9 + 7;
stack<char> op;
stack<ll> res;
string model = "+-*/()^";
string s;
queue<string> q;
int t;

int pri(char c) {
    if (c == '^')
        return 3;
    if (c == '*' || c == '/')
        return 2;
    if (c == '+' || c == '-')
        return 1;
    if (c == ')')
        return 0;
}

bool isop(char c) {
    for (int i = 0; i < 7; i++) {
        if (c == model[i])
            return true;
    }
    return false;
}

string char2string(char c) {
    string s = "";
    s += c;
    return s;
}
void ex_gcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return;
    }
    ex_gcd(b, a % b, x, y);
    ll t = x;
    x = y, y = t - (a / b) * y;
}
//当然你也可以这么写,更能体现公式:
//  ll X=x,Y=y;
//  x=Y,y=X-(a/b)*Y;
inline ll inv(ll a) {
    ll inv_a, y;
    ex_gcd(a, MAX, inv_a, y);
    return (inv_a % MAX + MAX) % MAX;
}

ll string2int(string s) {
    ll res = 0, flag = 1;
    if (s[0] == '-')
        flag = -1;
    ll i = (flag == -1) ? 1 : 0;
    for (; i < s.size(); i++) res = (res * 10 + s[i] - '0') % MAX;
    // cout<<s<<res<<endl;
    return res * flag % MAX;
}

ll quickpow(ll a, ll n) {
    ll res = 1;
    if (n < 0)
        n = (n + MAX) % MAX;
    while (n != 0) {
        if (n % 2 == 1)
            res = ((res % MAX) * (a % MAX)) % MAX;
        a = ((a % MAX) * (a % MAX)) % MAX;
        n /= 2;
    }
    return res % MAX;
}

ll calcul(queue<string> &q) {
    queue<string> mmm = q;
    // while(!mmm.empty()){
    // cout<<mmm.front();
    // mmm.pop();
    //}
    // cout<<endl;
    while (!res.empty()) res.pop();
    bool flag = true;
    ll a, b;
    while (!q.empty()) {
        string s = q.front();
        q.pop();
        if (s.size() == 1 && !(s[0] >= '0' && s[0] <= '9')) {
            if (!res.empty()) {
                b = res.top();
                res.pop();
            } else
                flag = false;
            if (!res.empty()) {
                a = res.top();
                res.pop();
            } else
                flag = false;
            ll sum;
            // cout<<a<<b<<s<<endl;
            if (s == "+")
                sum = ((a % MAX) + (b % MAX)) % MAX;
            else if (s == "-")
                sum = ((a % MAX) - (b % MAX)) % MAX;
            else if (s == "*")
                sum = ((a % MAX) * (b % MAX)) % MAX;
            else if (s == "^")
                sum = quickpow(a, b);
            else if (s == "/" && b == 0)
                flag = false;
            else
                sum = ((a % MAX) * (inv(b) % MAX)) % MAX;
            if (!flag)
                break;
            // cout<<sum<<endl;
            res.push(sum);
        } else
            res.push(string2int(s));
    }
    // cout<<res.size()<<endl;
    if (res.size() != 1 && flag)
        flag = false;
    if (!flag)
        return MAX;
    else
        return res.top();
}

void solve(string s) {
    bool flag = true;
    while (!q.empty()) q.pop();
    string tmp = "";
    while (!op.empty()) op.pop();
    for (int i = 0; i < s.size(); i++) {
        // cout<<s[0]<<endl;
        if (isop(s[i])) {
            if (tmp != "")
                q.push(tmp);
            if (s[i] == ')') {
                while (!op.empty() && op.top() != '(') {
                    q.push(char2string(op.top()));
                    op.pop();
                }
                if (op.empty())
                    flag = false;
                else
                    op.pop();
            } else if (s[i] == '(')
                op.push(s[i]);
            else if (s[i] == '^') {
                while (!op.empty() && pri(s[i]) < pri(op.top()) && op.top() != '(') {
                    q.push(char2string(op.top()));
                    op.pop();
                }
                op.push(s[i]);
            } else {
                while (!op.empty() && pri(s[i]) <= pri(op.top()) && op.top() != '(') {
                    q.push(char2string(op.top()));
                    op.pop();
                }
                op.push(s[i]);
            }
            tmp = "";
        } else if (s[i] != ' ')
            tmp += s[i];
    }
    if (tmp != "")
        q.push(tmp);
    while (!op.empty()) {
        if (op.top() == '(')
            flag = false;
        q.push(char2string(op.top()));
        op.pop();
    }
    ll fin = calcul(q);
    // cout<<fin<<flag<<endl;
    if (flag && fin != MAX)
        cout << (fin + MAX) % MAX << endl;
    else
        cout << "GG" << endl;
    return;
}

int main() {
    int t;
    string s;
    while (scanf("%d", &t) != EOF) {
        getchar();
        while (t--) {
            getline(cin, s);
            solve(s);
        }
    }
}

子任务 #1

Wrong Answer

得分：45

测试点 #1

Accepted

得分：100

用时：3 ms

内存：428 KiB

输入文件（1.in）

10
14/  5+2 * (3 - 1)
2^3 ^ 2
(2 ^ 3) ^ 2
5*2 ^ 5-4
( ((7 * (2 - 5) ) )/ 2 )
6 /0
1 ^ (3 - 4)
-1
2 +
<22 bytes omitted>

答案文件（1.out）

用户输出

系统信息

Exited with return code 0

测试点 #2

Accepted

得分：100

用时：3 ms

内存：236 KiB

输入文件（2.in）

5
(4- (  4)  )  -  0-6  -  (  9 )  /  0
8  -  9 / (  4^ 2 )
2  /  6  -  ( 6)
(7 +(  8-  9))
(3  - 1 
<17 bytes omitted>

答案文件（2.out）

用户输出

系统信息

Exited with return code 0

测试点 #3

Accepted

得分：100

用时：2 ms

内存：268 KiB

输入文件（3.in）

5
1  + 1 *2  +  1 ^1 *(5)
(9*0 ^17) * 3 +  4 *(4^2- (8))
(3  / ( 7/(3  )))^2^2 + (2 - 4) ^ 3 + (2 -3
<91 bytes omitted>

答案文件（3.out）

用户输出

系统信息

Exited with return code 0

测试点 #4

Accepted

得分：100

用时：2 ms

内存：232 KiB

输入文件（4.in）

5
(1 +0+( 10)  )-  (  9  )-  ( 17)
20* (  3 -( 19  +15)  )/ (8 - 11  +  6)
4 * 15 - ( 9  - 10+  (  5
<79 bytes omitted>

答案文件（4.out）

用户输出

系统信息

Exited with return code 0

测试点 #5

Accepted

得分：100

用时：3 ms

内存：260 KiB

输入文件（5.in）

5
7 -  ( 5*  (13+ 20  ) /  6 )  /  (7)
2^2^2^2
(20-(  6))
(17  * (1 ^20))
8 ^  ( 12  -  12  )

答案文件（5.out）

用户输出

系统信息

Exited with return code 0

测试点 #6

Wrong Answer

得分：0

用时：2 ms

内存：264 KiB

输入文件（6.in）

5
15 4-  15- 3 -20
13 +  14+ 15  12+ (17)
(18- 4  )  -17  (  19 -  0 *  12  -  11)
(14 *  1 - 20 +) 
<26 bytes omitted>

答案文件（6.out）

GG
GG
9
GG
1000000006

用户输出

116
1556
GG
GG
GG

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #7

Wrong Answer

得分：0

用时：2 ms

内存：368 KiB

输入文件（7.in）

10
20-(6)0+ (  12)*  3+ 10
6 +  14  - ( 20 + 19 )- 2+  0
(918* (19 /1-  11  ) )+ 19 +1  *  13 - 6
1*
<155 bytes omitted>

答案文件（7.out）

用户输出

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #8

Accepted

得分：100

用时：3 ms

内存：232 KiB

输入文件（8.in）

5
(16  +20-19-  10  )+ (14))
()9 +  15 )+(3  + 1 - (  15 * 8-  6))
12)- 14  -  3
0  /)  15  +( 0)/20
<48 bytes omitted>

答案文件（8.out）

GG
GG
GG
GG
GG

用户输出

GG
GG
GG
GG
GG

系统信息

Exited with return code 0

测试点 #9

Accepted

得分：100

用时：2 ms

内存：352 KiB

输入文件（9.in）

10
(7  -20 +10*  ( 7  +  ( 20 *  4  - (11 -2)(  -  )6  )+  6/  (  18-19  -(  (20))))
4- 7  /) 12 *( 
<361 bytes omitted>

答案文件（9.out）

GG
GG
GG
944444456
GG
GG
GG
GG
GG
494117629

用户输出

GG
GG
GG
944444456
GG
GG
GG
GG
GG
494117629

系统信息

Exited with return code 0

测试点 #10

Wrong Answer

得分：0

用时：2 ms

内存：360 KiB

输入文件（10.in）

20
284- 23 /397 ^)  727 736^  210/)  49 + 696
(770/  599 + (284  /57)  ) - 942  -(3  - 769  )^ 619  
<1568 bytes omitted>

答案文件（10.out）

GG
GG
GG
GG
GG
GG
GG
GG
GG
GG
GG
GG
269291130
GG
GG
GG
GG
GG
254204075
GG

用户输出

GG
GG
GG
GG
GG
GG
GG
GG
GG
GG
GG
GG
269291130
332575037
GG
GG
559613414
GG
254204075
GG

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #11

Wrong Answer

得分：0

用时：4 ms

内存：408 KiB

输入文件（11.in）

100
(5138^ 93361 *  79394  )*  56248  - 95527  ^(  98398-( 20828* 96534^  48902+80093  -  65211  /39
<42652 bytes omitted>

答案文件（11.out）

983666579
972863691
970685854
547723514
994123666
991268663
123396023
328396149
986785728
856072161

<801 bytes omitted>

用户输出

372496545
149678905
970685854
547723514
992643005
991268663
123396023
328396149
405860640
856072161
13987334
652563259
25375373

<778 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #12

Wrong Answer

得分：0

用时：4 ms

内存：360 KiB

输入文件（12.in）

100
(54556  /216/ 44373 ^ 6329  +  ( 80718  50256^  (8111  +67763 *26601  ^ 32325 / 50043)*  ( 89651
<42255 bytes omitted>

答案文件（12.out）

GG
73933213
87915419
814560269
574772325
732352216
916178829
171847350
300855690
434722427
36850519

<815 bytes omitted>

用户输出

GG
73933213
87915419
814560269
571738371
732352216
916178829
171847350
300855690
434722427
36850519
937678135
59880796
925010469
<787 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #13

Wrong Answer

得分：0

用时：4 ms

内存：356 KiB

输入文件（13.in）

100
16585-  42301/61828  /  ( 51096 + (  73132  ) /5619  + 49786  ^ ( 73501 /  (68692-14966*  67235 
<42833 bytes omitted>

答案文件（13.out）

940725600
865683700
89332149
GG
965277615
50032520
387847667
912407849
127311628
939349741
295542613
<828 bytes omitted>

用户输出

993752889
865683700
409021967
GG
38657825
50032520
387847667
912407849
959037377
939349741
295542613
GG
200265070
925883675
9773
<800 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #14

Wrong Answer

得分：0

用时：7 ms

内存：360 KiB

输入文件（14.in）

100
(1823692511^  (  2110167123 ) - 1751501957 +804611443  ^  1493169964*1305646732 -  14089142/1009
<119216 bytes omitted>

答案文件（14.out）

988417294
238601460
769056440
537157080
166278248
482153698
517927329
235195518
999599870
GG
3902855
<759 bytes omitted>

用户输出

306632234
188955303
769056440
537157080
767380771
482153698
517927329
745542052
999599870
GG
718957960
663077286
GG
384005376
95
<732 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #15

Wrong Answer

得分：0

用时：6 ms

内存：400 KiB

输入文件（15.in）

100
1471566 -  (  1461715* 1226218 / 1756328  /  ( 1366893- 1498465  +  1569659+ 1897109  + 1699172 
<94825 bytes omitted>

答案文件（15.out）

392549063
138700610
986907251
376592747
262559769
918025066
406108433
176619909
569354907
778079440

<863 bytes omitted>

用户输出

392549063
138700610
986907251
312039921
262559769
918025066
406108433
176619909
569354907
925945535
74730492
832964037
923331625
<829 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #16

Accepted

得分：100

用时：4 ms

内存：404 KiB

输入文件（16.in）

100
54903661  +  38776912+  23958361 -  (32256012-32073805+  2327029  +  59177449 ) -58242919 + 6146
<52007 bytes omitted>

答案文件（16.out）

56226665
999999860
GG
979038723
GG
999999814
2862506
999999647
999999824
151
999999465
786
750
503
6
<660 bytes omitted>

用户输出

56226665
999999860
GG
979038723
GG
999999814
2862506
999999647
999999824
151
999999465
786
750
503
6986657
11059148
1127
9306177
<632 bytes omitted>

系统信息

Exited with return code 0

测试点 #17

Wrong Answer

得分：0

用时：7 ms

内存：392 KiB

输入文件（17.in）

100
(51 *  85 /  66  /  ( 55  )* 13)  /65 /  96 *0/  ( 58 ) /( 47*58  *( 90 ) *(  1/80 *36/  79  /84
<52565 bytes omitted>

答案文件（17.out）

0
GG
GG
436373332
800648007
GG
947852070
398301791
GG
931589738
874089885
163868249
GG
GG
GG
2654491
<650 bytes omitted>

用户输出

0
GG
GG
436373332
800648007
GG
947852070
398301791
GG
931589738
874089885
163868249
GG
GG
GG
265449150
735268154
405663619
67427
<629 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #18

Accepted

得分：100

用时：5 ms

内存：412 KiB

输入文件（18.in）

100
(61131961  ^  6684911 )^41075565^ (  90178080 ) ^ 35322440 ^  76103233^ 73745469 ^ 10116220^  34
<53127 bytes omitted>

答案文件（18.out）

414884050
830959291
897735515
346842284
420680495
130692285
102953346
GG
987802810
501139416
8538725
<809 bytes omitted>

用户输出

414884050
830959291
897735515
346842284
420680495
130692285
102953346
GG
987802810
501139416
853872531
379542623
666381539
90342
<781 bytes omitted>

系统信息

Exited with return code 0

测试点 #19

Wrong Answer

得分：0

用时：6 ms

内存：348 KiB

输入文件（19.in）

100
430*  201 /  242/  318- 979^  (696  )  / 456 +  401 +613-  404 + 242  /893  *  773^  254 +  644 
<54325 bytes omitted>

答案文件（19.out）

464304022
GG
821460820
151189835
GG
772282869
484527161
473891091
GG
GG
GG
318725007
GG
GG
265331160
<736 bytes omitted>

用户输出

464304022
GG
821460820
16638178
GG
772282869
484527161
651201328
GG
GG
GG
318725007
GG
GG
849163054
799709562
999466695
68483764
<710 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #20

Wrong Answer

得分：0

用时：5 ms

内存：392 KiB

输入文件（20.in）

100
(949 ^  593-  905 *122+ 429  )  /  ( 35 / 337 /598) + 822 /  340*244)*(  186  )  / ( 59/ 696  )-
<55737 bytes omitted>

答案文件（20.out）

GG
639807163
903562843
114345019
192372474
324774636
GG
225486815
867267982
338101750
GG
709099205
G
<754 bytes omitted>

用户输出

GG
639807163
903562843
114345019
192372474
324774636
GG
182480236
598564366
338101750
GG
709099205
GG
GG
141540376
19275602
GG
5
<732 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0