QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#712637#9535. Arrow a Rowmegumi#AC ✓24ms16332kbC++142.5kb2024-11-05 16:28:102024-11-05 16:28:10

Judging History

This is the latest submission verdict.

  • [2024-11-05 16:28:10]
  • Judged
  • Verdict: AC
  • Time: 24ms
  • Memory: 16332kb
  • [2024-11-05 16:28:10]
  • Submitted

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
        f = (c == '-') ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9')
        x = x * 10 + c - 48, c = getchar();
    return f * x;
}
struct ans {
    int l, r, ll, rr;
} ans[500010];
int tot = 0;
int check(int a, int b) {
    int l1 = ans[a].l, l2 = ans[b].l, r1 = ans[a].r, r2 = ans[b].r;
    if (r1 + 3 >= l2 || r1 + 3 < l2)
        return 1;
    else
        return 0;
}
int fa[500010], son[500010];
vector<pair<int, int>> asw;
void dfs(int st) {
    if (st == 0)
        return;
    if (ans[st].rr)
        for (int i = ans[st].rr; i > ans[st].r + 3; i--) {
            asw.push_back({ans[st].l - 1, i});
        }
    for (int i = ans[st].ll; i < ans[st].l; i++) {
        asw.push_back({i, ans[st].r + 3});
    }
    dfs(son[st]);
}
signed main() {
    int T = read();
    while (T--) {
        string s;
        cin >> s;
        tot = 0;
        asw.clear();
        int n = s.size();
        s = ' ' + s;
        for (int i = 1; i <= n; i++)
            fa[i] = 0, son[i] = 0, ans[i] = {0, 0, 0, 0};
        if (s[1] != '>' || s[n] != '>') {
            cout << "No\n";
            continue;
        }
        int l = 0, r = 0, lstr = 0;
        for (int i = 1; i <= n; i++) {
            if (s[i] == '-') {
                if (l)
                    r++;
                else
                    l = i, r = i;
            } else {
                if (l) {
                    ans[++tot] = {l, r};
                    ans[tot].ll = lstr + 1;
                    lstr = r;
                }
                l = 0;
            }
            // cerr << i << ' ' << l << ' ' << r << endl;
        }
        ans[tot].rr = n;
        if (tot == 0 || ans[tot].r + 3 > n) {
            cout << "No\n";
            continue;
        }
        for (int i = 1; i < tot; i++) {
            int k = check(i, i + 1);
            if (k == 1)
                fa[i + 1] = i, son[i] = i + 1;
            else
                fa[i] = i + 1, son[i + 1] = i;
        }
        int st = 0;
        for (int i = 1; i <= tot; i++) {
            if (!fa[i]) {
                st = i;
                break;
            }
        }
        dfs(st);
        cout << "Yes" << ' ' << asw.size() << '\n';
        for (auto [x, y] : asw) {
            cout << x << ' ' << y - x + 1 << '\n';
        }
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 7892kb

input:

4
>>->>>
>>>->
>>>>>
>->>>>>>

output:

Yes 2
1 6
2 5
No
No
Yes 4
1 8
1 7
1 6
1 5

result:

ok ok (4 test cases)

Test #2:

score: 0
Accepted
time: 2ms
memory: 7692kb

input:

126
>->-->>>>
>--->->>>>
>--->-->>>
>>-->->>>
>>-->>>>>
>>->->>>>
>>->>->>>>
>-->->->>>
>->->>>>>>
>->>>
>->->>>>>
>>>->->>>
>>->>>>>>>
>>>>>->>>
>->>>->>>
>>--->->>>
>>->>>>
>->>>>->>>
>>>>-->>>
>---->>>
>>>---->>>
>>>>->>>>
>->>-->>>
>-->-->>>>
>>---->>>
>>--->>>
>->>>-->>>
>>-->>>>
>>---->>>>
>>-...

output:

Yes 3
1 5
3 7
3 6
Yes 3
1 7
5 6
5 5
Yes 2
1 7
5 6
Yes 3
1 7
2 6
5 5
Yes 4
2 8
2 7
1 7
2 6
Yes 4
1 6
2 5
4 6
4 5
Yes 5
1 6
2 5
5 6
4 6
5 5
Yes 3
1 6
4 5
6 5
Yes 5
1 5
3 8
3 7
3 6
3 5
Yes 1
1 5
Yes 4
1 5
3 7
3 6
3 5
Yes 4
1 7
2 6
3 5
5 5
Yes 6
2 9
2 8
2 7
2 6
1 6
2 5
Yes 5
1 9
2 8
3 7
4 6
5 5
Yes 4
1 ...

result:

ok ok (126 test cases)

Test #3:

score: 0
Accepted
time: 10ms
memory: 7700kb

input:

4032
>>--->>>>>>>>
>->>->->-->->>>
>>--->>--->>>
>>->->->>>>>>>>
>->---->->>>
>->>->>---->>>>
>>>>>>>>->>>>
>->>>--->>>->>>
>->>->>-->>>>>>
>->>-->---->>>
>-->--->>>->>>
>->---->>-->>>>
>>------>>>
>>>-->>--->>>>>
>->->->>-->>>>
>->->-->>->->>>
>>->>>>-->->>>>
>>>-->>->--->>>
>->->>>>>->>>>
>>-->->>...

output:

Yes 7
2 12
2 11
2 10
2 9
2 8
1 8
2 7
Yes 6
1 5
3 6
4 5
6 5
8 6
11 5
Yes 4
1 8
2 7
6 8
7 7
Yes 9
1 6
2 5
4 5
6 10
6 9
6 8
6 7
6 6
6 5
Yes 3
1 5
3 8
8 5
Yes 6
1 5
3 6
4 5
7 9
6 9
7 8
Yes 9
8 6
1 12
2 11
3 10
4 9
5 8
6 7
7 6
8 5
Yes 7
1 5
3 9
4 8
5 7
9 7
10 6
11 5
Yes 8
1 5
3 6
4 5
7 9
7 8
7 7
6 7
7 6
...

result:

ok ok (4032 test cases)

Test #4:

score: 0
Accepted
time: 8ms
memory: 7860kb

input:

10000
>>>>->->>->>->>>>
>->-->>->>->>>>>>
>->->>-->--->>>>>
>---->-->->>>>>>>
>->-->>--->>->>>>
>->>->>>>>>-->>>
>>--->->-->>->>>
>-->---->>>->>>
>->----->->->>>>>
>>--->---->-->>>>
>>-->->->--->>>
>----->>-->>->>>>
>-->->->>>>>->>>>
>>->>---->-->>>
>>->>-->>>-->>>
>------>->>>->>>>
>->->-->->>>->>>...

output:

Yes 10
1 8
2 7
3 6
4 5
6 5
8 6
9 5
12 6
11 6
12 5
Yes 9
1 5
3 6
6 6
7 5
10 8
10 7
10 6
9 6
10 5
Yes 7
1 5
3 5
5 7
6 6
9 9
9 8
9 7
Yes 7
1 8
6 6
9 9
9 8
9 7
9 6
9 5
Yes 7
1 5
3 6
6 8
7 7
12 6
11 6
12 5
Yes 9
1 5
3 6
4 5
6 11
7 10
8 9
9 8
10 7
11 6
Yes 6
1 8
2 7
6 5
8 6
11 6
12 5
Yes 5
1 6
4 8
9 7
10 ...

result:

ok ok (10000 test cases)

Test #5:

score: 0
Accepted
time: 24ms
memory: 7684kb

input:

10000
>>>-->>>>-->---->->->-->>>
>>-->>>>->-->>->>>
>->-->--->--->->-->>--->>->->>-->->->>>>>>->>>>----->->--->>----->>-->>>----->->->>>--->>->>-->->->->---->>->>>-->>->->>>->->>>>->>->->>-->>>->>->>-->>>>-->>-->>>->>->->>>--->>>-->>>--->>->->>>>>->->---->>>>->>>
->->>>>--->>>>>>->>>->>>>->->-->-->>...

output:

Yes 11
1 8
2 7
3 6
6 9
7 8
8 7
9 6
12 8
17 5
19 5
21 6
Yes 9
1 7
2 6
5 8
6 7
7 6
8 5
10 6
13 6
14 5
Yes 110
1 5
3 6
6 7
10 7
14 5
16 6
19 8
20 7
24 6
25 5
27 5
29 7
30 6
33 5
35 5
37 10
38 9
39 8
40 7
41 6
42 5
44 12
45 11
46 10
47 9
53 5
55 7
59 10
60 9
66 7
67 6
70 11
71 10
72 9
78 5
80 5
82 9
83 ...

result:

ok ok (10000 test cases)

Test #6:

score: 0
Accepted
time: 14ms
memory: 7864kb

input:

9999
->->--->>>>->->--->>--
->>>--->>>-->>--->>---
-->>>>>>>-
>>>->>>>>>>--
>>-->-->->----->->>>>->>->---->->
>-->->>>--->->->>->->-
>->--->--->>>>->>>----->------>>-->->>>
>>->>>->>>---->>>->>>>>>>>>->--->>->>>>>-->>>->->->>-->->--->->-->->>->->->>-->-->>>>>>>>--->>--->->>>-->->----->>-->->>--->-->...

output:

No
No
No
No
No
No
Yes 14
1 5
3 7
7 7
11 8
12 7
13 6
14 5
16 11
17 10
18 9
24 10
31 7
32 6
35 5
Yes 69
1 6
2 5
4 7
5 6
6 5
8 10
9 9
10 8
15 7
16 6
17 5
19 13
20 12
21 11
22 10
23 9
24 8
25 7
26 6
27 5
29 7
33 6
34 5
36 10
37 9
38 8
39 7
40 6
43 7
44 6
45 5
47 5
49 5
51 7
52 6
55 5
57 7
61 5
63 6
66 5...

result:

ok ok (9999 test cases)

Test #7:

score: 0
Accepted
time: 11ms
memory: 11312kb

input:

5
>-->>>>>--->->->>->>>>>->->-->-->->>>-->->--->>>------>->>-->>>------->>---->-->>>>>>-->>--->>-->->->>>>->-->------>>->>>>->>>-->---->--->>-->-->->--->->->->->>->-->->--->>>>->>->--->->>-->>>>>>->>>>->>--->->>-->>->->---->>>->->>->>->--->->->-->->>->->-->->------>>>->>>>>->>-->>->>>->>>>>----->---...

output:

No
No
Yes 48171
1 7
2 6
3 5
5 7
6 6
7 5
9 6
10 5
12 8
17 8
18 7
19 6
20 5
22 7
23 6
24 5
26 7
27 6
28 5
30 6
33 6
34 5
36 6
37 5
39 8
40 7
41 6
42 5
44 10
45 9
46 8
47 7
51 6
54 9
60 9
61 8
62 7
63 6
64 5
66 8
67 7
68 6
71 7
72 6
73 5
75 9
76 8
77 7
81 9
82 8
83 7
87 7
88 6
91 5
93 9
94 8
99 9
100 8...

result:

ok ok (5 test cases)

Test #8:

score: 0
Accepted
time: 24ms
memory: 16332kb

input:

5
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

No
Yes 99996
99995 6
1 99999
2 99998
3 99997
4 99996
5 99995
6 99994
7 99993
8 99992
9 99991
10 99990
11 99989
12 99988
13 99987
14 99986
15 99985
16 99984
17 99983
18 99982
19 99981
20 99980
21 99979
22 99978
23 99977
24 99976
25 99975
26 99974
27 99973
28 99972
29 99971
30 99970
31 99969
32 99968
...

result:

ok ok (5 test cases)

Test #9:

score: 0
Accepted
time: 18ms
memory: 8276kb

input:

20
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

Yes 24994
1 11298
2 11297
3 11296
4 11295
5 11294
6 11293
7 11292
8 11291
9 11290
10 11289
11 11288
12 11287
13 11286
14 11285
15 11284
16 11283
17 11282
18 11281
19 11280
20 11279
21 11278
22 11277
23 11276
24 11275
25 11274
26 11273
27 11272
28 11271
29 11270
30 11269
31 11268
32 11267
33 11266
34...

result:

ok ok (20 test cases)

Test #10:

score: 0
Accepted
time: 22ms
memory: 8096kb

input:

20
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...

output:

Yes 24996
2278 22723
2278 22722
2278 22721
2278 22720
2278 22719
2278 22718
2278 22717
2278 22716
2278 22715
2278 22714
2278 22713
2278 22712
2278 22711
2278 22710
2278 22709
2278 22708
2278 22707
2278 22706
2278 22705
2278 22704
2278 22703
2278 22702
2278 22701
2278 22700
2278 22699
2278 22698
2278...

result:

ok ok (20 test cases)

Extra Test:

score: 0
Extra Test Passed