QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#739144 | #9565. Birthday Gift | ewe | WA | 6ms | 5528kb | C++14 | 2.2kb | 2024-11-12 21:00:29 | 2024-11-12 21:00:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fopen \
freopen("E:/vscode/oi/in.txt", "r", stdin); \
freopen("E:/vscode/oi/out.txt", "w", stdout);
#define ios \
ios::sync_with_stdio(0); \
cin.tie(0);
#define i64 long long
#define ull unsigned i64
#define pii pair<int, int>
#define pdd pair<double, double>
#define ld long double
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define lowbit(x) (x & -x)
#define de(x) cout << #x << " = " << x << '\n'
#define MAXP 20
const int N = 2e5 + 10, M = 1e2 + 10;
const double eps = 1e-12;
const double PI = acos(-1);
bool Mst;
char s[N];
int stk[N], top;
int c[2], col[N];
void solve()
{
cin >> s + 1;
top = c[0] = c[1] = 0;
int n = strlen(s + 1);
for (int i = 1; i <= n; i++)
{
if (s[i] != '2' && top && s[stk[top]] == s[i])
--top;
else
stk[++top] = i;
}
for (int i = 1; i <= top; i++)
s[i] = s[stk[i]];
n = top, s[n + 1] = 0;
// cout << s + 1 << '\n';
int siz = 0;
for (int i = 1; i <= n; i++)
if (s[i] != '2')
{
col[i] = col[i - 1];
++c[col[i]];
}
else
{
int j = i;
while (s[j] == '2')
++j;
int len = j - i;
siz += len;
if (len & 1)
{
if (s[i - 1] != s[j])
col[j - 1] = col[i - 1] ^ 1;
else
col[j - 1] = col[i - 1];
}
else
{
if (s[i - 1] == s[j])
col[j - 1] = col[i - 1] ^ 1;
else
col[j - 1] = col[i - 1];
}
i = j - 1;
}
// for (int i = 1; i <= n; i++)
// cout << col[i] << " \n"[i == n];
cout << max(0, abs(c[0] - c[1]) - siz) << '\n';
}
bool Med;
signed main()
{
ios;
// fopen;
cerr << (&Med - &Mst) / 1024 / 1024;
int t = 1;
srand(time(0));
cout << fixed << setprecision(12);
cin >> t;
for (int i = 1; i <= t; i++)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3788kb
input:
5 0110101 01020102 0000021111 1012121010 0100202010
output:
3 4 0 6 0
result:
ok 5 number(s): "3 4 0 6 0"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3708kb
input:
50000 1010110101 1010101010 0101010101 0101010010 0101010010 1010101010 0101001010 1010010010 0100101010 1010101001 1010100101 0101010100 0100101011 0101101010 1011010110 1011010101 1010010101 1010010010 0101010101 0010101010 0101011010 0100101010 1010101010 1010010101 1010101101 1101010101 10100101...
output:
0 10 10 4 4 10 0 4 4 6 2 8 2 2 0 4 2 4 10 8 2 4 10 2 4 8 2 8 8 4 8 4 4 6 4 4 4 6 10 10 2 2 0 10 8 10 0 10 10 10 4 10 8 10 0 8 4 0 8 2 8 0 6 2 8 10 4 10 10 2 10 2 10 8 6 4 2 8 8 0 8 10 8 10 8 10 2 6 10 4 10 8 10 4 10 6 10 10 10 6 6 6 4 10 10 10 2 2 8 10 6 10 10 8 4 10 6 10 2 2 8 2 10 4 6 0 10 4 6 2 1...
result:
ok 50000 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 3848kb
input:
5000 1010101010101010101110101010101010100101010101010101010110101010101010101010101010101010101010101010 0101010101010101010101010101101010101010101010101010101010101010101010101010100101010101010110101010 010101010101010101010101010101010101010101010101010101010101010101010100101010101010101010101...
output:
58 16 44 26 2 30 62 14 16 68 44 78 58 54 52 4 22 60 12 60 12 82 64 68 44 4 34 12 82 16 64 12 14 46 48 12 94 12 82 50 30 40 8 88 62 20 2 46 86 36 16 20 18 74 66 36 80 98 26 0 30 72 40 70 28 80 52 18 94 62 32 26 18 92 44 80 48 4 28 32 34 50 80 54 80 32 62 62 76 70 78 16 16 2 2 58 46 18 56 26 36 56 76 ...
result:
ok 5000 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 3664kb
input:
500 01010101010101010101010101010101010101010101010101010101010101010101001010101010101010101010110101010101010101010101010101010101010101010100101101010101010010101010101010101010101010101010101010101010101010101010101010101101010101010101010101010101010101010101010101010101001010101010101001010100...
output:
28 12 76 174 24 124 142 142 142 194 216 70 12 176 18 310 16 188 38 42 164 110 162 4 12 24 2 96 206 4 238 64 64 28 50 54 278 182 122 86 4 76 44 146 118 122 276 268 148 32 78 90 202 40 20 240 128 116 228 282 36 178 160 88 2 20 114 70 248 68 54 18 18 210 46 126 26 52 0 298 6 16 160 32 92 56 106 126 246...
result:
ok 500 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
50 101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...
output:
836 3994 352 3984 1826 568 2088 4076 1750 1258 532 3036 1718 1106 1002 478 1838 2030 422 4210 828 2088 2930 4044 1406 2388 3586 2018 1976 1026 5092 4154 3478 1018 1998 4014 718 2852 6070 2518 6380 4826 170 1876 1096 3914 1692 574 4612 802
result:
ok 50 numbers
Test #6:
score: 0
Accepted
time: 2ms
memory: 3732kb
input:
50 010101010101101110100100101010101100010100110100101001011010101000100101001010100101101010001011010110010101010101010101011011000010001001010101010110101010111010011010101010100101001010101010101100101010101010100101010101010100011101110101010011010101011010110100110101010010010101101101011001010...
output:
152 84 110 60 218 124 190 198 76 98 202 234 126 160 236 134 44 324 176 136 178 156 46 220 8 106 18 136 346 74 30 104 310 264 160 224 198 218 314 166 166 54 82 246 242 62 164 26 336 124
result:
ok 50 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 4056kb
input:
2 0101010101010101010101010101010010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010...
output:
6648 174
result:
ok 2 number(s): "6648 174"
Test #8:
score: 0
Accepted
time: 6ms
memory: 3668kb
input:
50000 0100202010 0101221101 0120120101 1210102101 1210101020 1020210101 0200101020 1010210120 0121012010 0212101010 0201010120 1101010221 0012101020 1110101221 1010121201 1202010101 0210012101 0210010102 2101210101 0101002201 0102101210 1020101201 1201002101 0101022010 0201101012 1210010210 20120101...
output:
0 4 2 0 6 0 2 0 0 4 4 4 4 2 2 4 2 2 6 4 0 2 2 0 0 0 2 2 0 4 2 0 0 4 2 4 6 6 4 0 2 4 2 2 0 4 6 6 0 2 4 0 4 4 4 2 0 4 2 0 6 4 6 0 0 4 4 0 6 4 0 0 2 0 6 6 4 0 6 0 0 0 6 2 2 4 2 6 2 0 6 6 2 0 6 2 0 6 4 6 2 0 4 2 0 4 0 6 4 2 6 4 6 2 0 2 4 0 0 0 0 0 2 0 0 0 2 2 4 4 0 4 0 4 4 0 0 4 4 4 0 0 4 2 2 0 2 2 4 2 ...
result:
ok 50000 numbers
Test #9:
score: 0
Accepted
time: 3ms
memory: 3848kb
input:
5000 1010101012010101010112010120120102010110100101012101010100101010210101010201010100121010101201010110 0101010101102102010101010101010101010101012012210101010120101010101010120201010102010101010100012011 010201010101212010110201201010101210101010101010101010101101010110121010100101010101021010101...
output:
12 38 12 52 10 0 6 0 34 26 14 0 10 0 14 22 6 30 20 0 2 0 6 0 0 0 16 0 4 0 0 36 4 30 46 14 14 0 26 18 14 30 30 6 0 10 0 28 0 16 26 12 2 28 40 2 2 26 44 0 2 14 18 20 0 8 0 0 40 8 4 4 46 52 2 20 6 6 16 38 38 26 12 0 26 10 0 0 10 36 8 16 16 16 0 0 12 28 0 30 14 22 0 38 22 20 14 26 26 10 30 34 8 20 6 26 ...
result:
ok 5000 numbers
Test #10:
score: 0
Accepted
time: 4ms
memory: 3776kb
input:
5000 1210201012021010102101010101010101010102011010220101021010122112010101201012211201001220101020120101 1020102101011012200110101012021001010110101012010221010100222010201010121101010101201010201012221200 101010210110120101010210222101002102102100201012110101201010101101010220101010221001201010201...
output:
0 0 0 0 0 0 0 20 0 0 0 0 0 0 20 0 0 0 2 0 2 4 6 0 0 0 0 0 0 0 16 16 0 0 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 0 22 12 0 12 12 10 0 0 0 0 0 0 0 0 0 10 6 0 0 0 18 6 0 0 16 0 0 0 0 0 0 0 2 0 22 0 0 2 0 0 0 6 0 4 0 24 0 6 6 2 0 0 0 0 0 0 12 0 0 0 0 0 26 0 0 0 0 0 0 0 0 4 0 0 26 0 0 0 12 0 0 0 4 0 0 4 12 0 ...
result:
ok 5000 numbers
Test #11:
score: 0
Accepted
time: 3ms
memory: 3792kb
input:
500 01010101120101010101010101010101010101210101010101010101010101010101010101010101010101010101010101010102010101010101010101010101021010101010101010101201201010101010102201010110101101010120101010101010101010101010120101020101010101010102101010101010101210101012010101020101011010101010101010101010...
output:
138 178 0 0 30 0 0 68 56 174 0 0 38 72 46 0 0 250 266 58 140 122 124 24 98 0 0 0 126 106 34 64 6 132 0 20 90 370 86 134 12 308 106 158 8 98 128 0 30 52 100 218 222 0 0 100 36 38 34 50 110 0 114 42 148 92 94 138 142 0 90 0 0 76 176 0 148 0 250 92 114 102 26 0 0 156 52 0 104 0 32 18 46 84 0 8 64 0 72 ...
result:
ok 500 numbers
Test #12:
score: 0
Accepted
time: 2ms
memory: 3668kb
input:
500 10101010101010101010101010101001010101001010101010101010101010101010101001010101010101010101010101000101010101010101010101010100101010010010101001010101010100101010101010110101011101010101010101010101010101010101010101011010101010101010101010120101010101010201010101021010101010101010101010101010...
output:
16 30 136 200 304 56 20 88 10 36 64 158 92 196 30 298 314 248 0 158 144 310 166 120 10 0 76 232 20 2 128 100 126 154 58 102 116 16 214 62 212 208 44 14 186 22 0 52 118 28 94 140 130 58 94 214 148 34 56 192 62 82 28 100 58 132 36 202 6 92 0 120 192 166 144 52 76 172 68 254 14 58 274 94 226 162 42 44 ...
result:
ok 500 numbers
Test #13:
score: 0
Accepted
time: 4ms
memory: 3864kb
input:
500 10101010202010101010120201012010101010101010101010101201201010101010101010102210101010122121210101010210210101010101012010101010102201210101010102220102120101010101010122101210120121010120101010101020101201020201020101202201010102220101010101010101101012010101202012210101210101010101010101210101...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 0 0 0 0 0...
result:
ok 500 numbers
Test #14:
score: 0
Accepted
time: 2ms
memory: 3888kb
input:
50 101010121010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...
output:
3814 3524 2852 1062 1438 868 2466 3168 2894 2584 114 454 4056 1966 2978 2354 2348 3160 3824 4726 1080 168 894 810 3150 494 1298 1384 6540 1722 2342 4232 1810 2840 1122 1684 2742 1272 1814 188 2216 2742 2336 1648 388 1194 2286 3708 562 1784
result:
ok 50 numbers
Test #15:
score: 0
Accepted
time: 2ms
memory: 3864kb
input:
50 101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101001010101010101010101010101010101010101001010210101010010101010101201010101010101010101010101010101010101010101010101010101010101010101010...
output:
1912 458 0 592 0 1324 1472 518 6 750 0 1334 126 102 462 542 0 584 612 378 508 166 34 116 1252 508 526 32 74 208 136 70 636 1324 228 74 1804 0 666 272 284 232 322 634 862 896 104 292 480 100
result:
ok 50 numbers
Test #16:
score: 0
Accepted
time: 4ms
memory: 3892kb
input:
50 010201010101010101010101220102120121210101020101010210101010201210201010101220101212212010121010210101010101022010101010101010101012101010121221010102101010101022010101010101010101012021010102101202101012010220201010220101010101012101010101010120202021010101012010201021021010220101210101021202201...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 50 numbers
Test #17:
score: 0
Accepted
time: 2ms
memory: 3852kb
input:
50 010101010101010101010101010111010101011012101010101010101011010101010101010101010101011010101101010101010101010101010101101010101010121010201010101010221010101020101010101012101010110101010101121010101010010101010011010101010101101010101101010100101010102210212010101010101010101010010101010101010...
output:
184 306 0 0 0 0 422 0 396 0 0 0 2 0 172 0 0 0 0 0 0 0 0 108 0 50 182 0 0 48 64 410 360 0 0 42 0 806 330 260 0 96 0 0 132 0 0 404 100 0
result:
ok 50 numbers
Test #18:
score: 0
Accepted
time: 2ms
memory: 4488kb
input:
2 1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010...
output:
12306 14212
result:
ok 2 number(s): "12306 14212"
Test #19:
score: 0
Accepted
time: 2ms
memory: 4792kb
input:
2 0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010102010101010101010101010101010101010101010101010101010101010101010101...
output:
13352 522
result:
ok 2 number(s): "13352 522"
Test #20:
score: 0
Accepted
time: 3ms
memory: 5528kb
input:
2 1010101010101012101012122021201010101010210101010101010101202201010101010120102210220101010101010102101010101010101012101210101020101010220210101010101010101020101210101012010101201010201021010101012122121012010121012021010101201012010120101221010101201010101210101021021021010101010101012012010210...
output:
0 0
result:
ok 2 number(s): "0 0"
Test #21:
score: 0
Accepted
time: 3ms
memory: 5472kb
input:
2 0101010121012101012101010101010121010101010101010101010101010101010101010210120101010102101010220101210210101010101010101010101010210101021010101020101010101021210101010102101010101010101010101010101010101010210101010101010101010101010102101010101010101010101010101010120101220101010101010101010101...
output:
0 0
result:
ok 2 number(s): "0 0"
Test #22:
score: 0
Accepted
time: 5ms
memory: 3724kb
input:
50000 010101101 010100101 010101010 101010010 011010110 010101010 011010101 010100100 001010101 001010101 101010011 001010101 101010101 101010110 010101010 101010101 010101010 010110101 010100101 101010101 101010101 101010101 101010100 100101001 100101101 010101101 010100101 101010101 100100101 0010...
output:
3 1 9 3 1 9 5 3 7 7 5 7 9 5 9 9 9 1 1 9 9 9 7 1 1 3 1 9 3 3 7 9 5 7 5 9 9 7 5 5 3 9 9 1 5 9 1 5 7 1 5 7 9 9 3 7 5 7 3 7 3 9 9 5 3 3 1 9 5 5 1 3 5 3 9 3 7 3 9 9 5 7 7 3 1 9 9 9 7 5 9 9 9 9 9 5 5 3 7 7 9 9 3 9 9 1 1 9 5 7 3 5 1 5 5 9 9 7 1 3 9 7 1 9 9 5 9 7 5 7 7 7 3 9 3 1 5 9 5 1 5 1 9 5 3 9 9 3 9 3 ...
result:
ok 50000 numbers
Test #23:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
5000 010101010101010101010101010101010101010101011010101010101010101010101010100101010100101010100101010 101010101010101010101010101010101010101010101010101010110101010101010101010101010110101010101010101 10100101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010...
output:
21 45 91 35 31 71 95 41 65 19 87 99 33 73 27 33 7 11 97 53 55 43 15 87 35 99 97 9 51 37 83 3 53 89 81 21 49 21 91 3 49 13 37 75 45 89 57 1 95 95 19 71 69 13 23 25 39 85 51 99 43 11 73 99 7 9 37 7 55 9 25 61 11 57 81 29 53 79 47 49 41 31 21 65 43 67 9 5 21 41 87 59 19 67 79 95 63 83 75 65 89 27 39 39...
result:
ok 5000 numbers
Test #24:
score: 0
Accepted
time: 2ms
memory: 3672kb
input:
500 10101010101010101010010101010101010101010101010010101010101011010111010101010101010110101010101010101010101010101010110101010101010101010100101010101010101010101010101010101010101010100110110101010101010101001010101010101101010101010101010101010010101011010101010101010101010101010101001010110101...
output:
99 65 129 185 15 15 99 113 11 89 119 293 65 105 215 29 127 195 89 119 183 95 87 229 7 219 249 37 41 59 143 61 115 209 51 27 5 81 71 239 25 179 87 131 205 11 215 9 87 37 219 21 113 47 39 49 35 129 311 93 215 215 99 33 117 225 97 179 107 107 103 25 99 149 121 25 177 87 29 27 5 109 5 99 95 179 83 99 19...
result:
ok 500 numbers
Test #25:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
50 101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...
output:
955 2477 961 1029 249 1137 845 65 915 559 1593 457 1023 3465 3785 2839 1375 593 3927 3349 3273 1283 1563 3637 873 313 439 5929 4059 3567 4759 4793 535 1611 5251 1287 937 2057 483 4635 1193 4483 207 1375 493 2637 537 5 409 743
result:
ok 50 numbers
Test #26:
score: 0
Accepted
time: 2ms
memory: 3680kb
input:
50 011010010110101011100101010101001011010101001010101010110010101010101010110101010101010000101010101010010110110001001010100101101010101101010101110101010110101010101010100100101010110101010100101010101101001011001010101010010100010010010101010100010101010101010101010101010101011010101010010101010...
output:
193 157 463 51 261 83 31 153 123 3 65 271 435 147 83 325 39 47 315 73 309 177 71 239 111 243 301 49 43 119 91 115 251 235 121 89 405 431 309 139 177 41 39 17 121 233 161 3 57 129
result:
ok 50 numbers
Test #27:
score: 0
Accepted
time: 1ms
memory: 4052kb
input:
2 0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010110101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010...
output:
17045 1847
result:
ok 2 number(s): "17045 1847"
Test #28:
score: -100
Wrong Answer
time: 6ms
memory: 3780kb
input:
50000 010100122 110201201 101021012 202001001 102010102 012010102 101211020 201010102 012101012 010212010 211201010 001020120 121101012 210101210 012102101 102020101 101220101 121012010 101201210 011010220 102101020 010201210 101020120 210101021 101010220 012010102 011012012 010221010 202001011 2101...
output:
1 0 0 0 5 1 0 5 5 3 3 1 1 5 0 5 5 0 0 0 1 5 3 3 3 1 0 5 0 3 3 1 0 0 1 0 1 1 5 3 1 1 5 0 0 1 3 5 1 3 1 1 5 5 0 3 0 0 5 0 3 3 0 0 3 3 1 1 3 3 5 3 5 5 1 1 1 5 0 0 5 0 0 3 3 5 1 1 1 3 5 3 5 5 0 5 0 1 3 0 0 0 3 1 0 3 5 5 5 0 0 5 3 3 0 5 5 3 1 5 5 1 5 1 1 0 1 5 5 3 0 5 0 3 3 3 5 5 5 0 5 3 0 1 0 3 5 3 5 0 ...
result:
wrong answer 2nd numbers differ - expected: '1', found: '0'