oj.uz

Submission #149778

# Submission time Handle Problem Language Result Execution time Memory
149778 2019-09-01T07:09:19 Z Torat(#3726, Osama_Alkhodairy, mohammedehab2002, mahmoudbadawy) HicCup (FXCUP4_hiccup) C++17
24 / 100
 71 ms 55204 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 0;
    }
    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
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47232 KB Output is correct
2 Correct 34 ms 47360 KB Output is correct
3 Correct 31 ms 47360 KB Output is correct
4 Correct 37 ms 47744 KB Output is correct
5 Correct 69 ms 55204 KB Output is correct
6 Correct 44 ms 51320 KB Output is correct
7 Correct 41 ms 51320 KB Output is correct
8 Correct 67 ms 55204 KB Output is correct
9 Correct 71 ms 55204 KB Output is correct
10 Correct 39 ms 51328 KB Output is correct
11 Correct 31 ms 47352 KB Output is correct

Subtask #2
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47232 KB Output is correct
2 Correct 34 ms 47360 KB Output is correct
3 Correct 31 ms 47360 KB Output is correct
4 Correct 37 ms 47744 KB Output is correct
5 Correct 69 ms 55204 KB Output is correct
6 Correct 44 ms 51320 KB Output is correct
7 Correct 41 ms 51320 KB Output is correct
8 Correct 67 ms 55204 KB Output is correct
9 Correct 71 ms 55204 KB Output is correct
10 Correct 39 ms 51328 KB Output is correct
11 Correct 46 ms 51320 KB Output is correct
12 Correct 46 ms 51328 KB Output is correct
13 Correct 48 ms 51320 KB Output is correct
14 Correct 31 ms 47360 KB Output is correct
15 Correct 46 ms 51320 KB Output is correct
16 Incorrect 41 ms 47360 KB Output isn't correct
17 Halted 0 ms 0 KB -