QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#700883 | #9535. Arrow a Row | ucup-team3931# | AC ✓ | 26ms | 5936kb | C++14 | 2.6kb | 2024-11-02 13:30:02 | 2024-11-02 13:30:18 |
Judging History
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;
}
详细
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