QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#718302#9535. Arrow a RowfosovAC ✓17ms5188kbC++172.3kb2024-11-06 20:13:142024-11-06 20:13:14

Judging History

This is the latest submission verdict.

  • [2024-11-06 20:13:14]
  • Judged
  • Verdict: AC
  • Time: 17ms
  • Memory: 5188kb
  • [2024-11-06 20:13:14]
  • Submitted

answer

#include "bits/stdc++.h"
using namespace std;

#define ll long long 
#define INF 0x3f3f3f3f
#define LNF 0x3f3f3f3f3f3f3f3fll
#define MOD 998244353
#define pii pair<int, int>

#define N 200010

string rnd() {
    int n = random() % (30) + 5;
    string res = ">" + string(n-1, '*');
    for (int i = 1; i < n; ++ i) {
        res[i] =  (random() % 2) ? '>' : '-';
    }
    return res;
}

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t; cin >> t;
    while (t --) {
        string s; cin >> s;
        int n = s.size();

        vector<pii> ra;
        for (int i = 0, j = 0; i < n; j = ++ i) {
            if (s[i] != '>') continue;
            while (j < n && s[j] == '>') ++ j;
            ra.emplace_back(i, j);
            i = j-1;
        }

        bool f = 1;
        f &= s[0] == '>' && s.back() == '>';
        f &= ra.size() > 1;
        f &= ra.back().second - ra.back().first >= 3;

        if (!f) {
            cout << "No\n";
            continue;
        }

        vector<pii> res;
        for (int i = ra.size() - 1; i > 0; -- i) {
            if (ra[i].second - ra[i].first >= 3) {
                for (int j = ra[i].second - 3; j >= ra[i].first; -- j) {
                    res.emplace_back(0, j + 3);
                }
            }
        }
        for (int i = 0, j = 0; i < ra.size(); ++ i) {
            if (i == 0 || ra[i].second - ra[i].first < 3) {
                while (j <= i || ra[j].second - ra[j].first < 3) ++ j;
                for (int k = ra[i].first; k < ra[i].second; ++ k) {
                    res.emplace_back(k, ra[j].first + 3 - k);
                }
            }
        }

        cout << "Yes " << res.size() << '\n';
        for (auto [x, y] : res) cout << x+1 << ' ' << y << '\n';

        // string test = string(n, '*');
        // for (auto [x, y] : res) {
        //     for (int i = x; i < x + y; ++ i) {
        //         assert(y >= 5);
        //         test[i] = (i > x && i < x + y - 3) ? '-' : '>';
        //     }
        // }

        // if (s != test) {
        //     cout << s << '\n';
        //     cout << "wrong: " << test << '\n';
        //     break;
        // }
    }
}

詳細信息

Test #1:

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

input:

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

output:

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

result:

ok ok (4 test cases)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

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

output:

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

result:

ok ok (126 test cases)

Test #3:

score: 0
Accepted
time: 3ms
memory: 3624kb

input:

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

output:

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

result:

ok ok (4032 test cases)

Test #4:

score: 0
Accepted
time: 9ms
memory: 3560kb

input:

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

output:

Yes 11
1 17
1 16
1 16
2 15
3 14
4 13
6 11
8 9
9 8
11 6
12 5
Yes 10
1 17
1 16
1 15
1 14
1 14
3 12
6 9
7 8
9 6
10 5
Yes 8
1 17
1 16
1 15
1 15
3 13
5 11
6 10
9 7
Yes 8
1 17
1 16
1 15
1 14
1 13
1 13
6 8
9 5
Yes 8
1 17
1 16
1 16
3 14
6 11
7 10
11 6
12 5
Yes 8
1 16
1 11
1 10
1 9
1 8
1 8
3 6
4 5
Yes 7
1 16...

result:

ok ok (10000 test cases)

Test #5:

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

input:

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

output:

Yes 10
1 26
1 9
1 8
1 8
2 7
3 6
12 15
17 10
19 8
21 6
Yes 8
1 18
1 8
1 7
1 7
2 6
10 9
13 6
14 5
Yes 81
1 211
1 207
1 206
1 195
1 194
1 193
1 182
1 177
1 171
1 162
1 153
1 152
1 141
1 128
1 127
1 121
1 111
1 84
1 72
1 47
1 46
1 42
1 41
1 40
1 39
1 39
3 37
6 34
10 30
14 26
16 24
19 21
20 20
24 16
25 1...

result:

ok ok (10000 test cases)

Test #6:

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

input:

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

output:

No
No
No
No
No
No
Yes 11
1 39
1 18
1 14
1 13
1 13
3 11
7 7
24 16
31 9
32 8
35 5
Yes 54
1 129
1 102
1 89
1 88
1 87
1 86
1 85
1 84
1 45
1 40
1 39
1 38
1 27
1 26
1 25
1 24
1 23
1 22
1 21
1 17
1 10
1 6
1 6
2 5
29 10
33 6
34 5
47 38
49 36
51 34
52 33
55 30
57 28
61 24
63 22
66 19
68 17
69 16
71 14
73 12
...

result:

ok ok (9999 test cases)

Test #7:

score: 0
Accepted
time: 6ms
memory: 4556kb

input:

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

output:

No
No
Yes 36036
1 95948
1 95944
1 95943
1 95913
1 95897
1 95896
1 95895
1 95894
1 95893
1 95840
1 95839
1 95838
1 95833
1 95832
1 95831
1 95821
1 95779
1 95764
1 95752
1 95751
1 95750
1 95746
1 95715
1 95714
1 95710
1 95709
1 95700
1 95699
1 95698
1 95694
1 95688
1 95687
1 95686
1 95666
1 95665
1 95...

result:

ok ok (5 test cases)

Test #8:

score: 0
Accepted
time: 12ms
memory: 5188kb

input:

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

output:

No
Yes 99997
1 100000
1 99999
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
...

result:

ok ok (5 test cases)

Test #9:

score: 0
Accepted
time: 17ms
memory: 3792kb

input:

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

output:

Yes 24991
1 25000
1 24999
1 24998
1 24997
1 24996
1 24995
1 24994
1 24993
1 24992
1 24991
1 24990
1 24989
1 24988
1 24987
1 24986
1 24985
1 24984
1 24983
1 24982
1 24981
1 24980
1 24979
1 24978
1 24977
1 24976
1 24975
1 24974
1 24973
1 24972
1 24971
1 24970
1 24969
1 24968
1 24967
1 24966
1 24965
1 ...

result:

ok ok (20 test cases)

Test #10:

score: 0
Accepted
time: 15ms
memory: 4024kb

input:

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

output:

Yes 24997
1 25000
1 24999
1 24998
1 24997
1 24996
1 24995
1 24994
1 24993
1 24992
1 24991
1 24990
1 24989
1 24988
1 24987
1 24986
1 24985
1 24984
1 24983
1 24982
1 24981
1 24980
1 24979
1 24978
1 24977
1 24976
1 24975
1 24974
1 24973
1 24972
1 24971
1 24970
1 24969
1 24968
1 24967
1 24966
1 24965
1 ...

result:

ok ok (20 test cases)

Extra Test:

score: 0
Extra Test Passed