oj.uz

Submission #150558

# Submission time Handle Problem Language Result Execution time Memory
150558 2019-09-01T08:38:37 Z Weeeee(#3729, Alexa2001) HicCup (FXCUP4_hiccup) C++17
24 / 100
 108 ms 42788 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>=1; --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;

    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 19 ms 23936 KB Output is correct
2 Correct 20 ms 23936 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 25 ms 24576 KB Output is correct
5 Correct 104 ms 42788 KB Output is correct
6 Correct 32 ms 30764 KB Output is correct
7 Correct 36 ms 30756 KB Output is correct
8 Correct 108 ms 42660 KB Output is correct
9 Correct 105 ms 42788 KB Output is correct
10 Correct 34 ms 30764 KB Output is correct
11 Correct 22 ms 23856 KB Output is correct

Subtask #2
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23936 KB Output is correct
2 Correct 20 ms 23936 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 25 ms 24576 KB Output is correct
5 Correct 104 ms 42788 KB Output is correct
6 Correct 32 ms 30764 KB Output is correct
7 Correct 36 ms 30756 KB Output is correct
8 Correct 108 ms 42660 KB Output is correct
9 Correct 105 ms 42788 KB Output is correct
10 Correct 34 ms 30764 KB Output is correct
11 Correct 37 ms 32428 KB Output is correct
12 Correct 36 ms 32420 KB Output is correct
13 Correct 33 ms 30892 KB Output is correct
14 Correct 20 ms 23936 KB Output is correct
15 Correct 38 ms 34852 KB Output is correct
16 Incorrect 19 ms 23848 KB Output isn't correct
17 Halted 0 ms 0 KB -