207092026-01-08 18:07:10algoproDNScpp17Hibás válasz 2/40175ms15032 KiB
// UUID: fadec629-df40-42b6-b2cb-84e15e07120c
#include <bits/stdc++.h>
using namespace std;
string dns;
int n;
int solve(char c)
{
    int ans = 0;
    vector <int> v(n+1), p(n+1);
    unordered_map <int,int> m;
    vector <array <int,2>> t;
    for(int i = 1; i <= n; i++){
        if(dns[i] == c) v[i]++;
        else v[i]--;
    }
    for(int i = 1; i <= n; i++){
       p[i] = p[i-1] + v[i];
       if(m[p[i]] == 0) m[p[i]] = i;
    }

    for(auto [key, val] : m){
        t.push_back({key,val});
    }
    int INF = 2e9;
    t.push_back({-INF , 0});
    int T = t.size();
    sort(t.rbegin(),t.rend());
    vector <int> s(T,2e9);
    int mini = 2e9;
    for(int i = T-1; i > 0; i--){
        mini = min(mini, t[i][1]);
        s[i] = mini;
    }
    for(int i = 1; i <= n; i++){
        if(p[i] >= 0){
            ans = max(i, ans);
            continue;
        }
        int pos = 2e9;
        int l = 0, r = T-1;
        while(l <= r){
            int mid = (l+r)/2;
            if(t[mid][0] <= p[i]){
                pos = min(pos, mid);
                r = mid - 1;
            }
            else l = mid + 1;
        }
        if(pos == 2e9) continue;
        ans = max(ans, i-s[pos]);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> dns;
    n = dns.size();
    dns = ' ' + dns;
    int a = solve('A'), c = solve('C'), g = solve('G'), t = solve('T');
    cout << max(a,max(c,max(g,t)));

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base2/40
1Hibás válasz0/01ms508 KiB
2Hibás válasz0/0175ms9484 KiB
3Hibás válasz0/21ms316 KiB
4Hibás válasz0/21ms316 KiB
5Hibás válasz0/21ms316 KiB
6Elfogadva2/21ms316 KiB
7Hibás válasz0/22ms316 KiB
8Hibás válasz0/439ms2868 KiB
9Hibás válasz0/465ms4384 KiB
10Hibás válasz0/486ms4868 KiB
11Hibás válasz0/497ms6428 KiB
12Hibás válasz0/4101ms10920 KiB
13Hibás válasz0/5150ms13820 KiB
14Hibás válasz0/5165ms15032 KiB