Submission #150522

#	Time	Username	Problem	Language	Result	Execution time	Memory
150522		Weeeee (#200)	HicCup (FXCUP4_hiccup)	C++17	24 / 100	113 ms	42916 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];


void dfs(int node)
{
    for(auto it : v[node])
        dfs(it);

    int i;
    int last = pr[node];

    vector<pair<int,int>> intr;

    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;
    return X;
}

Compilation message (stderr)

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

• Subtask 1: 24 / 24
• Subtask 2: 0 / 76