oj.uz

Submission #149901

# Submission time Handle Problem Language Result Execution time Memory
149901 2019-09-01T07:22:06 Z Torat(#3726, Osama_Alkhodairy, mohammedehab2002, mahmoudbadawy) HicCup (FXCUP4_hiccup) C++17
24 / 100
 1000 ms 195492 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;
set <int> 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(auto &i : s){
        if(i == 'H') o = 0;
        else if(i == 'C') o = 1;
        else if(o == 0) 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'){
            for(int j = 0 ; j < x ; j++){
                auto it = g[h[i]].upper_bound(i);
                if(it == g[h[i]].end()) return 0;
                g[h[i]].erase(it);
            }
        }
    }
    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]].insert(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 57 ms 94328 KB Output is correct
2 Correct 55 ms 94208 KB Output is correct
3 Correct 58 ms 94328 KB Output is correct
4 Correct 62 ms 94592 KB Output is correct
5 Correct 91 ms 102188 KB Output is correct
6 Correct 67 ms 98168 KB Output is correct
7 Correct 73 ms 98296 KB Output is correct
8 Correct 94 ms 102180 KB Output is correct
9 Correct 97 ms 102180 KB Output is correct
10 Correct 66 ms 98168 KB Output is correct
11 Correct 60 ms 94328 KB Output is correct

Subtask #2
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 94328 KB Output is correct
2 Correct 55 ms 94208 KB Output is correct
3 Correct 58 ms 94328 KB Output is correct
4 Correct 62 ms 94592 KB Output is correct
5 Correct 91 ms 102188 KB Output is correct
6 Correct 67 ms 98168 KB Output is correct
7 Correct 73 ms 98296 KB Output is correct
8 Correct 94 ms 102180 KB Output is correct
9 Correct 97 ms 102180 KB Output is correct
10 Correct 66 ms 98168 KB Output is correct
11 Correct 63 ms 98296 KB Output is correct
12 Correct 61 ms 98304 KB Output is correct
13 Correct 67 ms 98168 KB Output is correct
14 Correct 69 ms 94332 KB Output is correct
15 Correct 74 ms 98168 KB Output is correct
16 Correct 67 ms 94328 KB Output is correct
17 Correct 58 ms 94336 KB Output is correct
18 Correct 65 ms 94588 KB Output is correct
19 Execution timed out 1110 ms 195492 KB Time limit exceeded
20 Halted 0 ms 0 KB -