QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19066#2117. Pandemia [B]Elegia0 12ms4100kbC++172.6kb2022-01-27 22:18:362022-05-06 03:51:10

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 03:51:10]
  • 评测
  • 测评结果：0
  • 用时：12ms
  • 内存：4100kb
查看
  • [2022-01-27 22:18:36]
  • 提交

answer

/*
_/_/_/_/    _/_/_/_/_/  _/_/_/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/  _/  _/
_/      _/  _/  _/    _/    _/_/
_/_/_/_/      _/_/     _/_/_/_/_/

_/_/_/_/    _/    _/  _/      _/
_/      _/   _/  _/   _/_/  _/_/
_/      _/    _/_/    _/ _/_/ _/
_/      _/     _/     _/  _/  _/
_/      _/    _/_/    _/      _/
_/      _/   _/  _/   _/      _/
_/_/_/_/    _/    _/  _/      _/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/
*/
#include <cassert>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int _ = 100005;

char s[_];
int cnt[_];

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T; cin >> T;
  while (T--) {
    int N; cin >> N >> (s + 1);
    fill(cnt, cnt + N + 1, 0);
    int lst = 0;
    for (int i = 1; i <= N; ++i) if (s[i] == '1') {
      if (lst == 0) ++cnt[i - 1];
      else {
        int len = i - lst - 1;
        ++cnt[len / 2]; ++cnt[(len + 1) / 2];
      }
      lst = i;
    }
    if (lst) ++cnt[N - lst];
    for (int i = N; i; --i) cnt[i - 1] += cnt[i];
    int ans = count(s + 1, s + N + 1, '1');
    for (int i = 1; i <= N; ++i) ans += max(cnt[i] - i, 0);
    cout << ans << '\n';
  }

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 1
Accepted
time: 0ms
memory: 3472kb

input:

3
8
00110100
10
1001000010
4
0000

output:

5
7
0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 3ms
memory: 3588kb

input:

165
3
001
5
01100
3
011
5
00111
11
00011011100
4
1110
5
00000
3
011
11
10111111011
11
00010100100
9
100000110
2
11
4
1000
5
11000
3
001
4
1001
1
0
3
110
10
0000001011
5
11100
2
01
7
0100000
8
10000001
3
001
1
0
1
0
4
1010
2
11
9
001100101
8
01001100
12
001110101000
8
10110011
2
01
5
00111
11
1101001...

output:

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

result:

ok 165 lines

Test #3:

score: -1
Wrong Answer
time: 1ms
memory: 3620kb

input:

104
10
0101101110
10
1110100100
8
10110101
8
10110010
11
11000111000
9
001011010
10
0101001010
10
1001000110
11
11011000010
9
001100001
9
000100110
12
011010100101
8
10010101
9
000010101
11
11001001010
8
10100010
8
00110010
10
1000100010
11
00011100111
8
11100010
11
11101100101
11
11110110110
8
1110...

output:

9
8
7
7
7
7
9
8
8
6
6
11
7
5
10
6
6
7
8
6
10
10
7
3
7
4
9
5
7
9
5
4
7
8
10
11
7
5
5
8
11
7
6
9
7
7
4
8
9
8
10
9
9
8
6
10
6
8
6
9
6
9
7
8
8
7
11
11
7
6
8
9
7
7
7
8
9
11
7
7
8
10
10
10
11
7
3
8
7
5
10
6
8
8
5
10
5
5
8
7
8
6
6
1

result:

wrong answer 18th lines differ - expected: '8', found: '7'

Subtask #2:

score: 0
Wrong Answer

Test #7:

score: 1
Accepted
time: 3ms
memory: 3676kb

input:

156
2
00
4
1011
5
01100
3
100
3
010
9
111100110
6
110101
7
1001001
10
0111100011
1
0
3
010
12
001010010000
11
00110001001
8
11111111
5
00011
8
11101011
8
00000011
5
10101
3
100
8
00000101
7
1101000
3
010
2
10
10
1011110110
8
11010000
4
1001
3
101
1
0
1
0
8
10010010
12
011101110000
12
100101110001
11...

output:

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

result:

ok 156 lines

Test #8:

score: -1
Wrong Answer
time: 3ms
memory: 3620kb

input:

97
9
001111001
9
010011011
10
1110110011
10
0010110001
11
01100100110
10
0100110111
11
01101110101
12
100111000100
11
01100100101
12
011011000110
11
01110011101
10
0101010101
11
01011100001
9
001110100
10
1110100100
11
00011011001
12
101101101100
9
101111011
11
01100110011
10
1001001010
9
011101101
...

output:

7
8
9
7
10
9
10
9
10
10
10
9
8
6
8
8
10
8
10
9
8
6
10
4
8
9
9
9
3
8
9
8
8
8
6
9
11
11
9
9
9
9
5
11
7
9
10
8
8
6
8
8
8
9
9
6
9
10
7
9
8
8
6
10
8
10
5
9
9
7
8
8
7
9
9
9
9
4
7
10
8
8
8
9
6
10
7
11
6
8
8
7
7
9
9
8
6

result:

wrong answer 90th lines differ - expected: '9', found: '8'

Subtask #3:

score: 0
Wrong Answer

Test #12:

score: 0
Wrong Answer
time: 0ms
memory: 3752kb

input:

187
52
1000111101110110110011011100100110100101001100101101
46
1100000110010100010101001000111101000000000110
62
00100011110000011000111010111111101100111101001001010011110111
76
1110001111001101110001011000100100001111110100010010100000111100011110101101
22
0001110010111010010011
22
001111000010110...

output:

50
37
58
72
19
19
32
49
84
46
17
93
23
57
81
57
83
80
75
38
87
53
78
88
33
25
31
1
86
69
0
48
4
57
63
63
56
22
53
17
90
22
73
40
76
37
95
11
34
63
13
77
81
41
38
2
86
16
90
9
1
44
42
44
34
40
58
93
61
29
24
79
21
56
70
60
13
49
90
57
53
94
43
81
44
83
63
58
59
56
53
66
41
81
9
24
31
2
14
43
18
65
87...

result:

wrong answer 10th lines differ - expected: '47', found: '46'

Subtask #4:

score: 0
Wrong Answer

Test #23:

score: 0
Wrong Answer
time: 3ms
memory: 3476kb

input:

191
58
0010001101010001101010001110000000011010010110111110100000
95
10101101001110010000111101000111010110010000111101001000000011110000000000111010010000010101111
38
11111000100001001111001101000111111000
55
1111010100011100001100110100101010010000100000001001110
92
1100110101100111010101010001101...

output:

48
84
34
49
89
7
81
56
81
47
54
6
39
70
14
89
89
35
64
39
45
72
3
74
42
68
46
31
45
65
30
53
45
53
9
76
72
22
32
83
36
77
9
54
29
46
49
83
15
17
18
35
8
93
63
68
47
16
88
7
55
6
84
93
21
70
36
19
17
89
19
40
92
2
89
37
30
7
5
20
76
8
83
40
93
1
92
2
9
88
46
29
67
18
78
46
39
18
18
4
80
19
67
96
30
3...

result:

wrong answer 5th lines differ - expected: '90', found: '89'

Subtask #5:

score: 0
Wrong Answer

Test #33:

score: 0
Wrong Answer
time: 4ms
memory: 3612kb

input:

419
340
0000110110111010111011000011010010001011101000101010110110111010001100110110101011111010110000001010111010100110000011000100011010011010101000110111011000110001000010001011111110001100100101100001001000110010111100100011010101100111101101001111111011101010001011100110000010000111110100011010...

output:

333
107
10
282
417
407
326
326
187
169
41
152
14
78
80
107
490
302
231
399
393
37
492
251
399
90
425
142
157
25
65
67
448
117
438
341
16
416
109
280
19
374
160
100
446
7
434
195
307
225
413
490
78
343
38
257
196
348
64
450
255
249
432
288
259
38
152
377
136
277
8
358
259
25
389
84
156
457
215
74
165...

result:

wrong answer 16th lines differ - expected: '108', found: '107'

Subtask #6:

score: 0
Wrong Answer

Test #44:

score: 0
Wrong Answer
time: 3ms
memory: 3700kb

input:

402
278
01101101111000111010111110001110100011001000000011100001000100110111000000001000100100100011110000001001010001101010010110001101101100001001111011110001111100100100101110000011011101000001100100011100111111011111011011011100110011111111111100111001001011000001110001000010010001
115
010001111...

output:

269
110
235
278
143
414
486
47
183
418
410
229
69
343
360
127
55
273
348
274
451
229
25
88
0
374
335
372
54
396
129
440
8
432
171
301
182
244
391
167
260
380
49
326
233
6
489
242
275
421
79
57
201
299
442
457
333
426
190
319
111
129
227
358
112
270
380
15
162
417
462
335
70
431
364
81
327
399
103
92...

result:

wrong answer 6th lines differ - expected: '415', found: '414'

Subtask #7:

score: 0
Wrong Answer

Test #55:

score: 0
Wrong Answer
time: 0ms
memory: 3760kb

input:

13
28591
111011011111010101011001111100110001010110011100101010011001010001010110001001100111100110001100011000000011011110011010100000100110010111110111001101010110100000010011000100101001011010000110010110001100110111101000101101011001100101101000110000110011110000001101101111110110110010001000010...

output:

28562
3405
12475
19028
16539
22927
10610
26329
9288
16613
8205
6234
19503

result:

wrong answer 4th lines differ - expected: '19029', found: '19028'

Subtask #8:

score: 0
Wrong Answer

Test #68:

score: 0
Wrong Answer
time: 5ms
memory: 3688kb

input:

7
30000
0000000001110010001001100101001101000001001011100001001000000010010010010001011000100100100100100100110001011000111110100010101011100101000001000011011000001100011001000000011101101000100000011100000110000100011010011001000100001100101110000001100010100000001000000111100110000100101110000001...

output:

29946
29943
29944
29944
29936
29936
19960

result:

wrong answer 6th lines differ - expected: '29937', found: '29936'

Subtask #9:

score: 0
Wrong Answer

Test #80:

score: 0
Wrong Answer
time: 10ms
memory: 4060kb

input:

23
66986
110000001011100111000101100110011000111010011000100100011100010110000011010111011011001000100110110101100010000110101000111010000110000100110101011010100111000011111001000101010101101010111011111110101001001011011010001001101011110111100100110110010100000100010011111011110011010110010011100...

output:

66963
1065
1931
31387
73868
60564
2576
7650
82367
46212
42769
25516
58535
21315
82200
47104
95979
85137
83905
41655
18423
6640
15697

result:

wrong answer 14th lines differ - expected: '21318', found: '21315'

Subtask #10:

score: 0
Wrong Answer

Test #93:

score: 0
Wrong Answer
time: 12ms
memory: 4100kb

input:

11
100000
00010101001000000000000000000101000000011010000000000100011101010011110000111100111100001001100000101110000100110001100001000100011111000110110000110000100111010010101100000100001101000101000010101000001000100000000100011111000001000100001000100100000111001000101011000101000010001001011000...

output:

99932
99938
99934
99922
99909
99936
99928
99934
99922
99920
6

result:

wrong answer 1st lines differ - expected: '99933', found: '99932'
English 繁體中文 简体中文

Server Time: 2024-12-02 06:49:26 | OpenSource Project