QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#700883#9535. Arrow a Rowucup-team3931#AC ✓26ms5936kbC++142.6kb2024-11-02 13:30:022024-11-02 13:30:18

Judging History

This is the latest submission verdict.

  • [2024-11-02 13:30:18]
  • Judged
  • Verdict: AC
  • Time: 26ms
  • Memory: 5936kb
  • [2024-11-02 13:30:02]
  • Submitted

answer

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define uint unsigned
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 100100;

int n;
char s[maxn];

namespace BIT {
	int c[maxn];
	
	inline void init() {
		for (int i = 0; i <= n; ++i) {
			c[i] = 0;
		}
	}
	
	inline void update(int x, int d) {
		for (int i = x; i <= n; i += (i & (-i))) {
			c[i] += d;
		}
	}
	
	inline void update(int l, int r, int x) {
		update(l, x);
		update(r + 1, -x);
	}
	
	inline int query(int x) {
		int res = 0;
		for (int i = x; i; i -= (i & (-i))) {
			res += c[i];
		}
		return res;
	}
}

inline bool check(int l, int r) {
	if (l - 1 < 1 || r + 3 > n) {
		return 0;
	}
	if (!BIT::query(l - 1) && s[l - 1] == '-') {
		return 0;
	}
	for (int i = 1; i <= 3; ++i) {
		if (!BIT::query(r + i) && s[r + i] == '-') {
			return 0;
		}
	}
	return 1;
}

void solve() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	if (s[1] == '-' || s[n - 2] == '-' || s[n - 1] == '-' || s[n] == '-') {
		puts("No");
		return;
	}
	BIT::init();
	vector<pii> vc;
	set<pii> vis;
	queue<pii> q;
	vector<pii> ans;
	for (int i = 1, j = 1; i <= n; i = (++j)) {
		if (s[i] == '>') {
			continue;
		}
		while (j < n && s[j + 1] == '-') {
			++j;
		}
		vc.pb(i, j);
		if (check(i, j)) {
			vis.emplace(i, j);
			q.emplace(i, j);
		}
	}
	if (vc.empty()) {
		puts("No");
		return;
	}
	while (q.size()) {
		pii p = q.front();
		q.pop();
		ans.pb(p.fst - 1, p.scd - p.fst + 5);
		BIT::update(p.fst - 1, p.scd + 3, 1);
		int x = lower_bound(vc.begin(), vc.end(), p) - vc.begin();
		if (x + 1 < (int)vc.size()) {
			pii u = vc[x + 1];
			if (check(u.fst, u.scd) && vis.find(u) == vis.end()) {
				vis.insert(u);
				q.push(u);
			}
		}
		if (x) {
			pii u = vc[x - 1];
			if (check(u.fst, u.scd) && vis.find(u) == vis.end()) {
				vis.insert(u);
				q.push(u);
			}
		}
	}
	if ((int)vis.size() < (int)vc.size()) {
		puts("No");
		return;
	}
	for (pii p : vc) {
		for (int i = p.scd + 4; i <= n; ++i) {
			if (BIT::query(i)) {
				break;
			}
			ans.pb(i - 4, 5);
		}
	}
	for (int i = vc[0].fst - 1; i; --i) {
		if (!BIT::query(i)) {
			ans.pb(i, 5);
		}
	}
	reverse(ans.begin(), ans.end());
	printf("Yes %d\n", (int)ans.size());
	for (pii p : ans) {
		printf("%d %d\n", p.fst, p.scd);
	}
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

Yes 2
1 5
2 5
No
No
Yes 4
4 5
3 5
2 5
1 5

result:

ok ok (4 test cases)

Test #2:

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

input:

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

output:

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

result:

ok ok (126 test cases)

Test #3:

score: 0
Accepted
time: 5ms
memory: 4136kb

input:

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

output:

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

result:

ok ok (4032 test cases)

Test #4:

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

input:

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

output:

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

result:

ok ok (10000 test cases)

Test #5:

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

input:

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

output:

Yes 8
1 5
2 5
9 6
12 8
17 5
19 5
21 6
3 6
Yes 5
1 5
8 5
10 6
14 5
2 6
Yes 58
190 5
37 5
36 5
1 5
3 6
6 7
10 7
84 7
14 5
89 5
16 6
92 6
20 7
95 5
47 9
25 5
128 5
97 5
53 5
27 5
195 5
182 7
162 5
141 5
131 5
111 6
99 5
72 9
55 7
30 6
197 5
187 5
165 5
153 6
144 5
133 5
121 5
115 5
101 8
78 5
60 9
33 5...

result:

ok ok (10000 test cases)

Test #6:

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

input:

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

output:

No
No
No
No
No
No
Yes 8
18 9
24 10
1 5
32 6
3 7
35 5
14 5
7 7
Yes 43
1 5
84 5
83 5
82 5
81 5
35 5
22 5
21 5
20 5
19 5
18 5
45 5
47 5
49 5
52 6
55 5
57 7
61 5
102 6
63 6
105 5
66 5
107 9
69 5
114 6
71 5
117 5
89 7
73 5
27 5
120 7
94 7
76 6
29 7
124 6
98 5
79 6
40 6
34 5
17 5
10 8
6 5
2 5
Yes 28
92 5
...

result:

ok ok (9999 test cases)

Test #7:

score: 0
Accepted
time: 26ms
memory: 5936kb

input:

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

output:

No
No
Yes 27013
1 5
2 5
95892 5
95891 5
95890 5
95835 5
95828 5
95747 5
95695 5
95683 5
95581 5
95570 5
95557 5
95556 5
95555 5
95554 5
95553 5
95552 5
95539 5
95517 5
95516 5
95464 5
95458 5
95457 5
95450 5
95449 5
95434 5
95433 5
95432 5
95417 5
95292 5
95291 5
95290 5
95279 5
95278 5
95277 5
9527...

result:

ok ok (5 test cases)

Test #8:

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

input:

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

output:

No
Yes 99996
1 5
2 5
3 5
4 5
5 5
6 5
7 5
8 5
9 5
10 5
11 5
12 5
13 5
14 5
15 5
16 5
17 5
18 5
19 5
20 5
21 5
22 5
23 5
24 5
25 5
26 5
27 5
28 5
29 5
30 5
31 5
32 5
33 5
34 5
35 5
36 5
37 5
38 5
39 5
40 5
41 5
42 5
43 5
44 5
45 5
46 5
47 5
48 5
49 5
50 5
51 5
52 5
53 5
54 5
55 5
56 5
57 5
58 5
59 5
6...

result:

ok ok (5 test cases)

Test #9:

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

input:

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

output:

Yes 24988
1 5
2 5
3 5
4 5
5 5
6 5
7 5
8 5
9 5
10 5
11 5
12 5
13 5
14 5
15 5
16 5
17 5
18 5
19 5
20 5
21 5
22 5
23 5
24 5
25 5
26 5
27 5
28 5
29 5
30 5
31 5
32 5
33 5
34 5
35 5
36 5
37 5
38 5
39 5
40 5
41 5
42 5
43 5
44 5
45 5
46 5
47 5
48 5
49 5
50 5
51 5
52 5
53 5
54 5
55 5
56 5
57 5
58 5
59 5
60 5...

result:

ok ok (20 test cases)

Test #10:

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

input:

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

output:

Yes 24996
1 5
2 5
3 5
4 5
5 5
6 5
7 5
8 5
9 5
10 5
11 5
12 5
13 5
14 5
15 5
16 5
17 5
18 5
19 5
20 5
21 5
22 5
23 5
24 5
25 5
26 5
27 5
28 5
29 5
30 5
31 5
32 5
33 5
34 5
35 5
36 5
37 5
38 5
39 5
40 5
41 5
42 5
43 5
44 5
45 5
46 5
47 5
48 5
49 5
50 5
51 5
52 5
53 5
54 5
55 5
56 5
57 5
58 5
59 5
60 5...

result:

ok ok (20 test cases)

Extra Test:

score: 0
Extra Test Passed