Wy Online Judge

WyOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#461	#83. 「NOIP2017」时间复杂度	Pigsyy	100	14ms	2012kb	C++23	2.6kb	2025-04-24 20:41:02	2025-04-24 20:41:04

answer

#include <cstdio>
#include <cstring>
using namespace std;

int t;
int L;

bool aborted;
bool nocnt;
int mxcnt;
int cnt;

char cbuf[11];
int clen, comp;
char buf[25];

char ao[7], ai[7], ax[10], ay[10];
int realx, realy;
struct stloop {
    char n;
    int i;
} st[107];
int scnt;
bool booked[26];

int main() {
    fgets(buf, 25, stdin);
    sscanf(buf, "%d", &t);

    while (t--) {
        memset(booked, 0, sizeof(booked));
        aborted = false;
        mxcnt = 0;
        nocnt = false;
        cnt = 0;
        scnt = 0;
        fgets(buf, 25, stdin);
        sscanf(buf, "%d%s", &L, cbuf);
        clen = strlen(cbuf);

        switch (clen - 4) {
        case 0:
            comp = 0;
            break;

        case 2:
            comp = cbuf[4] - '0';
            break;

        case 3:
            comp = (cbuf[4] - '0') * 10 + (cbuf[5] - '0');
            break;
        }

        for (int i = 1; i <= L; i++) {
            fgets(buf, 25, stdin);

            if (aborted)
                continue;

            sscanf(buf, "%s", ao);

            if (ao[0] == 'F') {
                sscanf(buf, "%s%s%s%s", ao, ai, ax, ay);
                realx = 0, realy = 0;
                sscanf(ax, "%d", &realx);
                sscanf(ay, "%d", &realy);

                if (booked[ai[0] - 'a'] == true) {
                    aborted = true;
                    continue;
                }

                booked[ai[0] - 'a'] = true;
                scnt++;
                st[scnt].n = ai[0];

                if ((realx == 0 && realy == 0) || (realx != 0 && realy != 0 && realx <= realy))
                    st[scnt].i = 0;
                else if (realx != 0 && realy == 0)
                    st[scnt].i = 1;
                else {
                    st[scnt].i = nocnt == true ? 0 : -1;
                    nocnt = true;
                }

                if (nocnt == false) {
                    cnt += st[scnt].i;

                    if (cnt > mxcnt)
                        mxcnt = cnt;
                }
            } else {
                if (scnt == 0) {
                    aborted = true;
                    continue;
                }

                if (nocnt == false)
                    cnt -= st[scnt].i;

                if (st[scnt].i == -1)
                    nocnt = false;

                booked[st[scnt].n - 'a'] = false;
                scnt--;
            }
        }

        if (aborted || scnt != 0)
            puts("ERR");
        else if (mxcnt == comp)
            puts("Yes");
        else
            puts("No");
    }
}

源文件, 语言: C++23

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 10

Accepted

time: 1ms

memory: 1912kb

input:

4
4 O(n^2)
F a 32 n
F b 69 n
E
E
2 O(n^2)
F a 60 n
E
4 O(n^4)
F a 67 n
F b 36 n
E
E
10 O(n^4)
F a 78...

output:

Yes
No
No
No

result:

ok 4 tokens

Test #2:

score: 10

Accepted

time: 1ms

memory: 1700kb

input:

2
8 O(n^2)
F a 57 n
F b 69 92
F c 85 87
F d 38 n
E
E
E
E
2 O(n^1)
F a 27 n
E

output:

Yes
Yes

result:

ok 2 tokens

Test #3:

score: 10

Accepted

time: 0ms

memory: 2012kb

input:

5
10 O(n^4)
F a 67 n
F b 20 n
F c 36 n
F d 32 n
F e 44 53
E
E
E
E
E
8 O(n^4)
F a 34 90
F b 79 n
F c ...

output:

Yes
No
Yes
No
No

result:

ok 5 tokens

Test #4:

score: 10

Accepted

time: 1ms

memory: 1764kb

input:

3
36 O(n^7)
F a 88 98
F b 29 n
E
E
F a 86 90
E
F a 14 15
F b 27 n
F c 69 n
F d 40 64
F e 61 87
F f 6...

output:

No
Yes
No

result:

ok 3 tokens

Test #5:

score: 10

Accepted

time: 2ms

memory: 1780kb

input:

3
48 O(n^10)
F a 87 n
F b 39 n
F c 26 n
F d 5 n
E
E
F e 35 n
F f 81 n
F g 32 n
F h 45 55
F i 16 n
F ...

output:

Yes
Yes
No

result:

ok 3 tokens

Test #6:

score: 10

Accepted

time: 2ms

memory: 1860kb

input:

2
54 O(n^9)
F a 8 n
F b 60 62
F c 20 n
F d 81 n
F e 70 n
F f 78 n
E
E
E
E
E
E
F a 76 n
F b 34 n
F c ...

output:

No
Yes

result:

ok 2 tokens

Test #7:

score: 10

Accepted

time: 1ms

memory: 1908kb

input:

3
44 O(n^3)
F a 42 50
F b 42 n
F c 39 77
F d 61 99
F e 36 37
F f n 28
F g 26 n
F h n 1
F i 68 n
F j ...

output:

Yes
Yes
Yes

result:

ok 3 tokens

Test #8:

score: 10

Accepted

time: 2ms

memory: 1952kb

input:

5
56 O(n^10)
F a 13 n
F b 80 n
F c 43 49
F d 52 n
F e 79 84
F f 27 n
F g 87 n
F h 56 n
F i 4 n
F j 4...

output:

Yes
ERR
ERR
No
ERR

result:

ok 5 tokens

Test #9:

score: 10

Accepted

time: 2ms

memory: 1808kb

input:

5
42 O(n^12)
F a 24 n
F b 43 n
F c 38 n
F d 88 n
F e 13 55
F f 26 50
F g 30 99
E
E
E
E
E
E
E
F a 60 ...

output:

No
No
Yes
ERR
ERR

result:

ok 5 tokens

Test #10:

score: 10

Accepted

time: 2ms

memory: 1852kb

input:

9
22 O(n^7)
F a 70 94
F b 90 94
E
E
F a 29 n
F b 22 n
F c 4 27
F d 85 n
F e 24 n
F f 56 87
F g 19 66...

output:

ERR
ERR
ERR
Yes
No
Yes
Yes
Yes
No

result:

ok 9 tokens