QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#784940#9535. Arrow a RowHansAC ✓24ms4680kbC++232.4kb2024-11-26 16:24:032024-11-26 16:24:03

Judging History

This is the latest submission verdict.

  • [2024-11-26 16:24:03]
  • Judged
  • Verdict: AC
  • Time: 24ms
  • Memory: 4680kb
  • [2024-11-26 16:24:03]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

void solve() {
  string s;
  cin >> s;
  if (s[0] != '>') {
    cout << "No\n";
    return;
  }
  for (int i = s.size()-3; i < s.size(); i++) {
    if (s[i] != '>') {
      cout << "No\n";
      return;
    }
  }

  bool has_stick = false;
  for (char c : s) {
    if (c == '-') {
      has_stick = true;
      break;
    }
  }

  if (!has_stick) {
    cout << "No\n";
    return;
  }
  

  vector<int> starts, lengths;
  stack<int> start_e, length_e;
  int head_idx = s.size();

  int arrow_heads = 0;

  bool consecutive_heads = true;

  int i = 1;
  int tail_idx = 0;

  while (s[i-1] == '>') {
    starts.push_back(i);
    lengths.push_back(s.size()-i+1);
    i++;
  }
  tail_idx = i-1;

  // i is 1-indexed
  for (i = s.size()-3; i > tail_idx; i--) {
    
    // If it is arrow head
    if (s[i-1] == '>') {
      arrow_heads++;
      // Make a new arrow from 1 to this arrow head.
      if (arrow_heads == 3) {

        while (start_e.size()) {
          starts.push_back(start_e.top());
          lengths.push_back(length_e.top());
          start_e.pop();
          length_e.pop();
        }

        starts.push_back(tail_idx);
        lengths.push_back(i+3 - tail_idx);
        head_idx = i+2;

        consecutive_heads = true;
        arrow_heads = 0;
      }

    } 
    // If it is a stick, we determine whether to make an end or a start
    else {
      if (consecutive_heads && arrow_heads) {
        starts.push_back(tail_idx);
        lengths.push_back(i+4 - tail_idx);
        head_idx = i+3;
      } else {
        for (int x = arrow_heads; x >= 1; x--) {
          start_e.push(i+x);
          length_e.push(head_idx - i - x + 1);
        }
      }

      arrow_heads = 0;
      consecutive_heads = false;
    }
  }

  // cout << "Remaining arrow heads: " << arrow_heads << '\n';

  for (int x = arrow_heads; x >= 1; x--) {
    start_e.push(1+x);
    length_e.push(head_idx - x);
  }

  while (start_e.size()) {
    starts.push_back(start_e.top());
    lengths.push_back(length_e.top());
    start_e.pop();
    length_e.pop();
  }


  cout << "Yes " << starts.size() << '\n';
  for (int i = 0; i < starts.size(); i++) {
    cout << starts[i] << ' ' << lengths[i] << '\n';
  }
}


int main() {
  int n; cin >> n;
  while (n--)
    solve();

}

详细

Test #1:

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

input:

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

output:

Yes 2
1 6
2 5
No
No
Yes 2
1 8
1 5

result:

ok ok (4 test cases)

Test #2:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

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

output:

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

result:

ok ok (126 test cases)

Test #3:

score: 0
Accepted
time: 4ms
memory: 3536kb

input:

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

output:

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

result:

ok ok (4032 test cases)

Test #4:

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

input:

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

output:

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

result:

ok ok (10000 test cases)

Test #5:

score: 0
Accepted
time: 19ms
memory: 3796kb

input:

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

output:

Yes 9
1 26
2 25
3 24
12 15
17 10
19 8
21 6
3 7
3 6
Yes 7
1 18
2 17
10 9
13 6
14 5
2 7
2 6
Yes 77
1 211
1 207
1 206
197 10
199 8
1 195
1 193
186 8
187 7
189 5
1 182
1 177
1 171
164 8
165 7
167 5
1 162
156 7
157 6
1 153
1 152
143 10
144 9
146 7
147 6
1 141
130 12
131 11
133 9
135 7
136 6
1 128
1 127
1...

result:

ok ok (10000 test cases)

Test #6:

score: 0
Accepted
time: 23ms
memory: 3536kb

input:

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

output:

No
No
No
No
No
No
Yes 10
1 39
24 16
31 9
32 8
35 5
1 18
1 14
1 13
3 11
7 7
Yes 45
1 129
2 128
105 25
107 23
113 17
114 16
117 13
119 11
120 10
124 6
2 101
93 10
94 9
98 5
2 88
2 85
2 83
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
75 10
76 9
79 6
2 44
2 39
2 37
29 10...

result:

ok ok (9999 test cases)

Test #7:

score: 0
Accepted
time: 13ms
memory: 3972kb

input:

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

output:

No
No
Yes 33334
1 95948
2 95947
3 95946
3 95942
3 95941
95915 29
95916 28
95922 22
95924 20
95928 16
95930 14
95931 13
95933 11
95935 9
95936 8
95938 6
3 95911
95901 13
95903 11
95906 8
95908 6
3 95895
3 95892
3 95891
95842 52
95848 46
95862 32
95864 30
95866 28
95867 27
95871 23
95872 22
95874 20
9...

result:

ok ok (5 test cases)

Test #8:

score: 0
Accepted
time: 16ms
memory: 4680kb

input:

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

output:

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

result:

ok ok (5 test cases)

Test #9:

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

input:

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

output:

Yes 15862
1 25000
2 24999
3 24998
4 24997
5 24996
6 24995
7 24994
8 24993
9 24992
10 24991
11 24990
12 24989
13 24988
14 24987
15 24986
16 24985
17 24984
18 24983
19 24982
20 24981
21 24980
22 24979
23 24978
24 24977
25 24976
26 24975
27 24974
28 24973
29 24972
30 24971
31 24970
32 24969
33 24968
34...

result:

ok ok (20 test cases)

Test #10:

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

input:

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

output:

Yes 9851
1 25000
2 24999
3 24998
4 24997
5 24996
6 24995
7 24994
8 24993
9 24992
10 24991
11 24990
12 24989
13 24988
14 24987
15 24986
16 24985
17 24984
18 24983
19 24982
20 24981
21 24980
22 24979
23 24978
24 24977
25 24976
26 24975
27 24974
28 24973
29 24972
30 24971
31 24970
32 24969
33 24968
34 ...

result:

ok ok (20 test cases)

Extra Test:

score: 0
Extra Test Passed