QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#162839#244. Turn Off The LightSolitaryDream#100 ✓274ms24308kbC++141.6kb2023-09-03 17:07:222023-09-03 17:07:24

Judging History

你现在查看的是最新测评结果

  • [2023-09-03 17:07:24]
  • 评测
  • 测评结果:100
  • 用时:274ms
  • 内存:24308kb
  • [2023-09-03 17:07:22]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int p = 1e9 + 7;
const int N = 1e6 + 10;
int n;
char s[N];
int f[N][2];
inline void Solve(int ans[N]) {
    static int a[N];
    for (int i = 1; i <= n; ++i) a[i] = (s[i] == '1');
    int bp = 0, ep;
    for (int i = 1; i <= n; ++i) if (a[i]) {
        if (!bp) bp = i;
        ep = i;
    }
    f[ep][1] = 2;
    f[ep][0] = 1;
    for (int i = ep - 1; i; --i) {
        for (int j = 0; j < 2; ++j) {
            f[i][j] = f[i + 1][j ^ a[i] ^ 1] + 2 * j + 1;
        }
    }
    for (int i = 1, cost = 0, last = 0; i < ep; ++i) 
        if (i <= bp) {
            ans[i] = f[i + 1][a[i]];
        } else {
            ans[i] = (i - bp) + cost + f[i][last];
            cost += (last == 1 ? 3 : 1);
            last ^= 1 ^ !a[i];
        }
    for (int i = ep; i <= n; ++i) ans[i] = 1e9;
    if (bp == ep) ans[ep] = 3;
    // printf("%s\n", s + 1);
    // for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
    // puts("");
}
int ans[2][N];
int main() {
    int Case;
    scanf("%d", &Case);
    while (Case--) {
        scanf("%d%s", &n, s + 1);
        if (find(s + 1, s + n + 1, '1') == s + n + 1) {
            puts("0");
            continue;
        }
        for (int round = 0; round < 2; ++round) {
            Solve(ans[round]);
            reverse(s + 1, s + n + 1);
        }
        int rst = 0;
        for (int i = 1; i <= n; ++i) {
            rst = (rst + 1ll * i * min(ans[0][i], ans[1][n - i + 1])) % p;
        }
        printf("%d\n", rst);
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 274ms
memory: 24308kb

input:

146645
2
00
2
10
2
01
2
11
3
000
3
100
3
010
3
110
3
001
3
101
3
011
3
111
4
0000
4
1000
4
0100
4
1100
4
0010
4
1010
4
0110
4
1110
4
0001
4
1001
4
0101
4
1101
4
0011
4
1011
4
0111
4
1111
5
00000
5
10000
5
01000
5
11000
5
00100
5
10100
5
01100
5
11100
5
00010
5
10010
5
01010
5
11010
5
00110
5
10110
5...

output:

0
5
7
6
0
14
10
12
14
24
12
26
0
34
22
36
18
40
20
38
26
60
40
58
24
62
42
60
0
69
47
66
33
80
50
83
31
90
60
93
34
87
57
80
45
120
90
123
64
117
87
110
42
123
93
120
67
118
88
129
0
123
89
126
63
128
86
125
49
150
108
147
70
153
111
152
51
168
126
165
88
171
129
170
54
165
123
168
85
154
112
159
73...

result:

ok 146645 lines