QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#787598#9565. Birthday Giftucup-team1266WA 9ms3832kbC++201.5kb2024-11-27 13:23:212024-11-27 13:23:21

Judging History

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

  • [2024-11-27 13:23:21]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:3832kb
  • [2024-11-27 13:23:21]
  • 提交

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'