QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#787598 | #9565. Birthday Gift | ucup-team1266 | WA | 9ms | 3832kb | C++20 | 1.5kb | 2024-11-27 13:23:21 | 2024-11-27 13:23:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// #define int ll
#define endl '\n'
const int MAX = 5e5 + 5, mod = 1e9 + 7;
void solve(){
// int n; cin >> n;
string s; cin >> s;
int n = s.size();
vector<int> a(n);
for (int i = 0; i < n; i ++){
a[i] = s[i] - '0' + 1;
}
vector<int> d2(n);
vector<array<int, 2>> p;
for (int i = 0, l = 0, r = -1; i < n; i ++ ){
int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
while (0 <= i - k - 1 && i + k < n && (a[i - k - 1] & a[i + k])) k ++;
d2[i] = k--;
if (i + k > r){
l = i - k - 1, r = i + k;
if (l <= r)
p.push_back({l, r});
}
}
sort(p.begin(), p.end(), [](array<int, 2> a, array<int, 2> b){
return a[1] < b[1];
});
vector<int> dp(p.size() + 1);
if (dp.empty()) cout << n << endl;
else{
int m = p.size();
for (int i = 1; i <= m; i ++){
int lk = 0, rk = i - 1;
while (lk < rk){
int mid = (lk + rk + 1) >> 1;
if (mid == 0 or p[mid - 1][1] < p[i - 1][0]) lk = mid;
else rk = mid - 1;
}
dp[i] = max(dp[i - 1], dp[lk] + p[i - 1][1] - p[i - 1][0] + 1);
}
cout << n - dp.back() << endl;
}
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T=1;cin>>T;while(T--)
solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
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: -100
Wrong Answer
time: 9ms
memory: 3832kb
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:
wrong answer 255th numbers differ - expected: '2', found: '4'