oj.uz

Submission #149755

# Submission time Handle Problem Language Result Execution time Memory
149755 2019-09-01T07:06:52 Z Torat(#3726, Osama_Alkhodairy, mohammedehab2002, mahmoudbadawy) HicCup (FXCUP4_hiccup) C++17
0 / 100
 36 ms 47360 KB 
#include <bits/stdc++.h>
#include "hiccup.h"
//~ #include "grader.cpp"
using namespace std;

const int N = 1000001;

int n;
string s;
vector <int> h, v[N], g[N];

bool valid(){
    int o = 0;
    for(auto &i : s){
        o += i == 'H';
        o -= i == 'C';
        if(o < 0) return -1;
    }
    if(o) return 0;
    for(int i = 0 ; i < n ; i++){
        if(s[i] == 'H' && s[i + 1] == '!') return 0;
    }
    return 1;
}
bool check(int x){
    for(int i = 0 ; ; i++){
        if((int)v[i].size() == 0) break;
        g[i] = v[i];
    }
    for(int i = n - 1 ; i >= 0 ; i--){
        if(s[i] == 'C'){
            int cur = x;
            while(cur > 0 && g[h[i]].size() && g[h[i]].back() > i){
                g[h[i]].pop_back();
                cur--;
            }
            if(cur) return 0;
        }
    }
    return 1;
}
int HicCup(std::string S) {
    s = S;
    n = s.size();
    if(!valid() || s == string(n, '!')) return -1;
    h.resize(n);
    h[0] = 1;
    for(int i = 1 ; i < n ; i++){
        h[i] = h[i - 1];
        if(s[i] == 'H') h[i]++;
        else if(s[i] == 'C') h[i]--;
        else v[h[i]].push_back(i);
    }
    int l = 0, r = n;
    while(l <= r){
        int mid = (l + r) / 2;
        if(check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    return l - 1;
}

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47360 KB Output is correct
2 Incorrect 36 ms 47352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47360 KB Output is correct
2 Incorrect 36 ms 47352 KB Output isn't correct
3 Halted 0 ms 0 KB -