Submission #150583

#	Time	Username	Problem	Language	Result	Execution time	Memory
150583		Weeeee (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	116 ms	42880 KiB

hiccup

#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 (stderr)

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 / 24
• Subtask 2: 76 / 76