提交记录 #24074

编号	题目	状态	分数	总时间	内存	代码 / 答案文件	提交者	提交时间
#24074	#1137. JM的算术表达式（3）	Wrong Answer	75	87 ms	388 K	C++ 11 / 4.6 K	pcw0118	2020-03-18 20:06:54

显示原始代码

#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 = 1, b = 1;
    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();
            }
            if (!res.empty()) {
                a = res.top();
                res.pop();
            }
            ll sum;
            // cout<<a<<b<<s<<endl;
            if (s == "+")
                sum = ((a % MAX) + (b % MAX)) % MAX;
            else if (s == "-")
                sum = (a - 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 (!flag)
        return MAX;
    else
        return res.top();
}

void solve(string s) {
    bool flag = true;
    int num = 0, operat = 0, left = 0, right = 0;
    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);
                // cout<<tmp<<endl;
                num++;
            }
            if (s[i] == ')') {
                right++;
                while (!op.empty() && op.top() != '(') {
                    q.push(char2string(op.top()));
                    op.pop();
                }
                if (!op.empty())
                    op.pop();
            } else if (s[i] == '(') {
                op.push(s[i]);
                left++;
            } else if (s[i] == '^') {
                operat++;
                while (!op.empty() && pri(s[i]) < pri(op.top()) && op.top() != '(') {
                    q.push(char2string(op.top()));
                    op.pop();
                }
                op.push(s[i]);
            } else {
                operat++;
                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] == ' ') {
            if (tmp != "") {
                q.push(tmp);
                tmp = "";
                num++;
            }
        } else
            tmp += s[i];
    }
    if (tmp != "") {
        q.push(tmp);
        // cout<<tmp<<endl;
        num++;
    }
    while (!op.empty()) {
        q.push(char2string(op.top()));
        op.pop();
    }
    ll fin = calcul(q);
    // cout<<fin<<flag<<endl;
    // cout<<num<<operat<<left<<right<<endl;
    if (((num - 1) != operat) || (left != right) || fin == MAX)
        flag = false;
    if (flag)
        cout << (fin + MAX) % MAX << endl;
    else
        cout << "GG" << endl;
    return;
}

int main() {
    int t;
    string s;
    // freopen("11.in","r",stdin);
    while (scanf("%d", &t) != EOF) {
        getchar();
        while (t--) {
            getline(cin, s);
            solve(s);
        }
    }
}

子任务 #1

Wrong Answer

得分：75

测试点 #1

Accepted

得分：100

用时：4 ms

内存：324 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

内存：264 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

用时：3 ms

内存：352 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

用时：3 ms

内存：348 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

用时：2 ms

内存：360 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

内存：304 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

用户输出

GG
GG
GG
42
GG

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #7

Wrong Answer

得分：0

用时：3 ms

内存：356 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

内存：268 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

内存：236 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

Accepted

得分：100

用时：3 ms

内存：280 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
GG
GG
GG
GG
GG
254204075
GG

系统信息

Exited with return code 0

测试点 #11

Accepted

得分：100

用时：5 ms

内存：248 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>

用户输出

983666579
972863691
970685854
547723514
994123666
991268663
123396023
328396149
986785728
856072161
144338517
652563259
25375373
<773 bytes omitted>

系统信息

Exited with return code 0

测试点 #12

Accepted

得分：100

用时：6 ms

内存：352 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
574772325
732352216
916178829
171847350
300855690
434722427
36850519
509554043
59880796
925010469
<787 bytes omitted>

系统信息

Exited with return code 0

测试点 #13

Accepted

得分：100

用时：5 ms

内存：364 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>

用户输出

940725600
865683700
89332149
GG
965277615
50032520
387847667
912407849
127311628
939349741
295542613
GG
540562335
925883675
9773
<800 bytes omitted>

系统信息

Exited with return code 0

测试点 #14

Wrong Answer

得分：0

用时：7 ms

内存：356 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>

用户输出

988417294
238601460
769056440
537157080
166278248
482153698
517927329
235195518
999599870
GG
390285565
663077286
GG
384005376
95
<738 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #15

Wrong Answer

得分：0

用时：7 ms

内存：388 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
376592747
262559769
918025066
406108433
176619909
569354907
778079440
873677325
832964037
92333162
<828 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #16

Accepted

得分：100

用时：5 ms

内存：372 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

Accepted

得分：100

用时：5 ms

内存：348 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
<622 bytes omitted>

系统信息

Exited with return code 0

测试点 #18

Wrong Answer

得分：0

用时：9 ms

内存：348 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
<788 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #19

Accepted

得分：100

用时：5 ms

内存：356 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
151189835
GG
772282869
484527161
473891091
GG
GG
GG
318725007
GG
GG
265331160
799709562
999466695
6848376
<708 bytes omitted>

系统信息

Exited with return code 0

测试点 #20

Accepted

得分：100

用时：5 ms

内存：352 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
225486815
867267982
338101750
GG
709099205
GG
GG
141540376
445217267
GG

<726 bytes omitted>

系统信息

Exited with return code 0