QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#710745 | #9535. Arrow a Row | WA_automaton# | AC ✓ | 22ms | 7172kb | C++23 | 2.4kb | 2024-11-04 21:21:43 | 2024-11-04 21:21:44 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb push_back
void debug() {std::cerr << "\n";}
template<class T, class... OtherArgs>
void debug(T &&var, OtherArgs &&... args) {
std::cerr << std::forward<T>(var) << " ";
debug(std::forward<OtherArgs>(args)...);
}
#define SZ(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using i64 = long long;
using u64 = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
constexpr int N = 200010;
constexpr int P = 998244353;
void solve() {
string s;
cin >> s;
int n = SZ(s);
if (!(s[0] == '>' && s.substr(n - 3) == ">>>") || s.find('-') == -1) {
cout << "No\n";
return;
}
vector<PII> res1, res2;
string t(n, '*');
const string arrow = ">->>>";
auto nxtj = [&](int i) {
int j = i;
while (j < n && s[j] == '-') {
j++;
}
return j;
};
auto color = [&](int l, int r) {
// debug("?", l, r);
assert(r - l + 1 >= 5 && l >= 0 && r < n);
t[l] = t[r] = t[r - 1] = t[r - 2] = '>';
for (int i = l + 1; i <= r - 3; i++) {
t[i] = '-';
}
};
for (int i = 1; i < n - 3; i++) {
if (s[i] == '-') {
int j = nxtj(i);
res2.pb({i - 1, j + 2 - (i - 1) + 1});
i = j;
} else if (s[i - 1] == '>' && s[i] == '>') {
res2.pb({i - 1, 5});
}
}
set<PII> st;
for (int i = n - 5; i >= 0; i--) {
if (s[i + 1] == '-') {
break;
}
st.insert({i, 5});
res1.pb({i, 5});
}
while (SZ(res2) && st.contains(res2.back())) {
res2.pop_back();
}
cout << "Yes " << SZ(res1) + SZ(res2) << '\n';
for (const auto &[p, l] : res1) {
cout << p + 1 << ' ' << l << '\n';
color(p, p + l - 1);
}
for (const auto &[p, l] : res2) {
cout << p + 1 << ' ' << l << '\n';
color(p, p + l - 1);
}
// debug("?", s, t);
assert(s == t);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(20);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3832kb
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: 3544kb
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 5 5 4 5 1 5 2 6 Yes 4 5 5 1 5 2 5 4 5 Yes 5 6 5 1 5 2 5 4 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 6 5 5 5 4 5 3 5 1 5 2 5 Yes 5 1 5 2 5 3 5 4 5 5 5 Yes 4 1 ...
result:
ok ok (126 test cases)
Test #3:
score: 0
Accepted
time: 3ms
memory: 3628kb
input:
4032 >>--->>>>>>>> >->>->->-->->>> >>--->>--->>> >>->->->>>>>>>> >->---->->>> >->>->>---->>>> >>>>>>>>->>>> >->>>--->>>->>> >->>->>-->>>>>> >->>-->---->>> >-->--->>>->>> >->---->>-->>>> >>------>>> >>>-->>--->>>>> >->->->>-->>>> >->->-->>->->>> >>->>>>-->->>>> >>>-->>->--->>> >->->>>>>->>>> >>-->->>...
output:
Yes 7 9 5 8 5 7 5 6 5 5 5 1 5 2 7 Yes 6 1 5 3 5 4 5 6 5 8 6 11 5 Yes 4 1 5 2 7 6 5 7 7 Yes 9 11 5 10 5 9 5 8 5 7 5 1 5 2 5 4 5 6 5 Yes 3 1 5 3 8 8 5 Yes 6 11 5 1 5 3 5 4 5 6 5 7 8 Yes 9 9 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 Yes 7 1 5 3 5 4 5 5 7 9 5 10 5 11 5 Yes 8 11 5 10 5 9 5 1 5 3 5 4 5 6 5 7 6 Ye...
result:
ok ok (4032 test cases)
Test #4:
score: 0
Accepted
time: 9ms
memory: 3604kb
input:
10000 >>>>->->>->>->>>> >->-->>->>->>>>>> >->->>-->--->>>>> >---->-->->>>>>>> >->-->>--->>->>>> >->>->>>>>>-->>> >>--->->-->>->>> >-->---->>>->>> >->----->->->>>>> >>--->---->-->>>> >>-->->->--->>> >----->>-->>->>>> >-->->->>>>>->>>> >>->>---->-->>> >>->>-->>>-->>> >------>->>>->>>> >->->-->->>>->>>...
output:
Yes 10 13 5 1 5 2 5 3 5 4 5 6 5 8 5 9 5 11 5 12 5 Yes 9 13 5 12 5 11 5 1 5 3 6 6 5 7 5 9 5 10 5 Yes 7 13 5 12 5 1 5 3 5 5 5 6 6 9 7 Yes 7 13 5 12 5 11 5 10 5 1 8 6 6 9 5 Yes 7 13 5 1 5 3 6 6 5 7 7 11 5 12 5 Yes 9 1 5 3 5 4 5 6 5 7 5 8 5 9 5 10 5 11 6 Yes 6 1 5 2 7 6 5 8 6 11 5 12 5 Yes 5 1 6 4 8 9 5...
result:
ok ok (10000 test cases)
Test #5:
score: 0
Accepted
time: 12ms
memory: 3684kb
input:
10000 >>>-->>>>-->---->->->-->>> >>-->>>>->-->>->>> >->-->--->--->->-->>--->>->->>-->->->>>>>>->>>>----->->--->>----->>-->>>----->->->>>--->>->>-->->->->---->>->>>-->>->->>>->->>>>->>->->>-->>>->>->>-->>>>-->>-->>>->>->->>>--->>>-->>>--->>->->>>>>->->---->>>>->>> ->->>>>--->>>>>>->>>->>>>->->-->-->>...
output:
Yes 11 1 5 2 5 3 6 6 5 7 5 8 5 9 6 12 8 17 5 19 5 21 6 Yes 9 1 5 2 6 5 5 6 5 7 5 8 5 10 6 13 5 14 5 Yes 110 1 5 3 6 6 7 10 7 14 5 16 6 19 5 20 7 24 5 25 5 27 5 29 5 30 6 33 5 35 5 37 5 38 5 39 5 40 5 41 5 42 5 44 5 45 5 46 5 47 9 53 5 55 7 59 5 60 9 66 5 67 6 70 5 71 5 72 9 78 5 80 5 82 5 83 5 84 7 ...
result:
ok ok (10000 test cases)
Test #6:
score: 0
Accepted
time: 13ms
memory: 3640kb
input:
9999 ->->--->>>>->->--->>-- ->>>--->>>-->>--->>--- -->>>>>>>- >>>->>>>>>>-- >>-->-->->----->->>>>->>->---->-> >-->->>>--->->->>->->- >->--->--->>>>->>>----->------>>-->->>> >>->>>->>>---->>>->>>>>>>>>->--->>->>>>>-->>>->->->>-->->--->->-->->>->->->>-->-->>>>>>>>--->>--->->>>-->->----->>-->->>--->-->...
output:
No No No No No No Yes 14 1 5 3 7 7 7 11 5 12 5 13 5 14 5 16 5 17 5 18 9 24 10 31 5 32 6 35 5 Yes 69 1 5 2 5 4 5 5 5 6 5 8 5 9 5 10 8 15 5 16 5 17 5 19 5 20 5 21 5 22 5 23 5 24 5 25 5 26 5 27 5 29 7 33 5 34 5 36 5 37 5 38 5 39 5 40 6 43 5 44 5 45 5 47 5 49 5 51 5 52 6 55 5 57 7 61 5 63 6 66 5 68 5 69...
result:
ok ok (9999 test cases)
Test #7:
score: 0
Accepted
time: 11ms
memory: 5304kb
input:
5 >-->>>>>--->->->>->>>>>->->-->-->->>>-->->--->>>------>->>-->>>------->>---->-->>>>>>-->>--->>-->->->>>>->-->------>>->>>>->>>-->---->--->>-->-->->--->->->->->>->-->->--->>>>->>->--->->>-->>>>>>->>>>->>--->->>-->>->->---->>>->->>->>->--->->->-->->>->->-->->------>>>->>>>>->>-->>->>>->>>>>----->---...
output:
No No Yes 48171 1 5 2 5 3 5 5 5 6 5 7 5 9 5 10 5 12 8 17 5 18 5 19 5 20 5 22 5 23 5 24 5 26 5 27 5 28 5 30 6 33 5 34 5 36 5 37 5 39 5 40 5 41 5 42 5 44 5 45 5 46 5 47 7 51 6 54 9 60 5 61 5 62 5 63 5 64 5 66 5 67 5 68 6 71 5 72 5 73 5 75 5 76 5 77 7 81 5 82 5 83 7 87 5 88 6 91 5 93 5 94 8 99 5 100 8 ...
result:
ok ok (5 test cases)
Test #8:
score: 0
Accepted
time: 16ms
memory: 7172kb
input:
5 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
No Yes 99996 99996 5 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 ...
result:
ok ok (5 test cases)
Test #9:
score: 0
Accepted
time: 22ms
memory: 5352kb
input:
20 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
Yes 24994 24996 5 24995 5 24994 5 24993 5 24992 5 24991 5 24990 5 24989 5 24988 5 24987 5 24986 5 24985 5 24984 5 24983 5 24982 5 24981 5 24980 5 24979 5 24978 5 24977 5 24976 5 24975 5 24974 5 24973 5 24972 5 24971 5 24970 5 24969 5 24968 5 24967 5 24966 5 24965 5 24964 5 24963 5 24962 5 24961 5 24...
result:
ok ok (20 test cases)
Test #10:
score: 0
Accepted
time: 21ms
memory: 5328kb
input:
20 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>...
output:
Yes 24996 24996 5 24995 5 24994 5 24993 5 24992 5 24991 5 24990 5 24989 5 24988 5 24987 5 24986 5 24985 5 24984 5 24983 5 24982 5 24981 5 24980 5 24979 5 24978 5 24977 5 24976 5 24975 5 24974 5 24973 5 24972 5 24971 5 24970 5 24969 5 24968 5 24967 5 24966 5 24965 5 24964 5 24963 5 24962 5 24961 5 24...
result:
ok ok (20 test cases)
Extra Test:
score: 0
Extra Test Passed