QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#712637 | #9535. Arrow a Row | megumi# | AC ✓ | 24ms | 16332kb | C++14 | 2.5kb | 2024-11-05 16:28:10 | 2024-11-05 16:28:10 |
Judging History
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';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
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