oj.uz

Submission #150896

# Submission time Handle Problem Language Result Execution time Memory
150896 2019-09-01T10:16:54 Z Alexa2001 HicCup (FXCUP4_hiccup) C++17
100 / 100
 125 ms 42852 KB 
#include "hiccup.h"
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e6 + 5;

int ap[Nmax], st[Nmax], nr, pr[Nmax];
int X = 1e9;
vector<int> v[Nmax];
bool bad = 0;

void dfs(int node)
{
    if(v[node].empty()) return;

    for(auto it : v[node])
        dfs(it);
    int i;
    int last = pr[node];

    vector<pair<int,int>> intr;

    if(ap[node] - ap[v[node][0]] > 0) bad = 1;

    for(i=(int)v[node].size()-1; i>=0; --i)
    {
        intr.push_back({pr[v[node][i]] + 1, last - 1});
        last = v[node][i];
    }

    int sum = 0;
    for(i=0; i<intr.size(); ++i)
    {
        sum += ap[intr[i].first] - ap[intr[i].second+1];
        assert(intr[i].second - intr[i].first + 1 == ap[intr[i].first] - ap[intr[i].second+1]);
        X = min(X, sum / (i+1));
    }
}

bool init(string &S)
{
    int i, n = S.size();
    nr = 0;

    S = '#' + S;

    for(i=n; i>=0; --i) ap[i] = ap[i+1] + (S[i] == '!');

    for(i=1; i<=n; ++i)
        if(S[i] == 'C')
        {
            if(!nr) return 0;
            pr[i] = st[nr];
            pr[st[nr]] = i;
            v[st[nr-1]].push_back(st[nr]);
            --nr;
        }
        else if(S[i] == 'H') st[++nr] = i;

    if(nr) return 0;
    pr[0] = n+1;
    pr[n+1] = 0;

    dfs(0);
    return 1;
}

int HicCup(string S)
{
    if(!init(S))
        return -1;
    if(bad) return -1;
    return X;
}

Compilation message

hiccup.cpp: In function 'void dfs(int)':
hiccup.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<intr.size(); ++i)
              ~^~~~~~~~~~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 27 ms 24568 KB Output is correct
5 Correct 124 ms 42756 KB Output is correct
6 Correct 38 ms 30628 KB Output is correct
7 Correct 37 ms 30500 KB Output is correct
8 Correct 124 ms 42808 KB Output is correct
9 Correct 125 ms 42852 KB Output is correct
10 Correct 37 ms 30628 KB Output is correct
11 Correct 23 ms 23800 KB Output is correct

Subtask #2
76.0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 23 ms 23800 KB Output is correct
4 Correct 27 ms 24568 KB Output is correct
5 Correct 124 ms 42756 KB Output is correct
6 Correct 38 ms 30628 KB Output is correct
7 Correct 37 ms 30500 KB Output is correct
8 Correct 124 ms 42808 KB Output is correct
9 Correct 125 ms 42852 KB Output is correct
10 Correct 37 ms 30628 KB Output is correct
11 Correct 44 ms 32292 KB Output is correct
12 Correct 45 ms 32448 KB Output is correct
13 Correct 43 ms 30884 KB Output is correct
14 Correct 23 ms 23800 KB Output is correct
15 Correct 42 ms 34724 KB Output is correct
16 Correct 24 ms 23928 KB Output is correct
17 Correct 24 ms 23760 KB Output is correct
18 Correct 30 ms 24440 KB Output is correct
19 Correct 42 ms 34596 KB Output is correct
20 Correct 43 ms 34852 KB Output is correct
21 Correct 40 ms 32292 KB Output is correct
22 Correct 43 ms 30296 KB Output is correct
23 Correct 38 ms 30628 KB Output is correct
24 Correct 43 ms 35108 KB Output is correct
25 Correct 92 ms 39100 KB Output is correct
26 Correct 63 ms 35748 KB Output is correct
27 Correct 46 ms 32676 KB Output is correct
28 Correct 39 ms 30976 KB Output is correct
29 Correct 38 ms 30756 KB Output is correct
30 Correct 24 ms 23896 KB Output is correct
31 Correct 23 ms 23800 KB Output is correct
32 Correct 25 ms 24552 KB Output is correct
33 Correct 23 ms 23800 KB Output is correct