oj.uz

Submission #150522

# Submission time Handle Problem Language Result Execution time Memory
150522 2019-09-01T08:34:48 Z Weeeee(#3729, Alexa2001) HicCup (FXCUP4_hiccup) C++17
24 / 100
 113 ms 42916 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];


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

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.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23936 KB Output is correct
2 Correct 21 ms 23936 KB Output is correct
3 Correct 21 ms 23680 KB Output is correct
4 Correct 24 ms 24576 KB Output is correct
5 Correct 106 ms 42660 KB Output is correct
6 Correct 34 ms 30756 KB Output is correct
7 Correct 36 ms 30764 KB Output is correct
8 Correct 113 ms 42916 KB Output is correct
9 Correct 107 ms 42792 KB Output is correct
10 Correct 33 ms 30756 KB Output is correct
11 Correct 19 ms 23808 KB Output is correct

Subtask #2
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23936 KB Output is correct
2 Correct 21 ms 23936 KB Output is correct
3 Correct 21 ms 23680 KB Output is correct
4 Correct 24 ms 24576 KB Output is correct
5 Correct 106 ms 42660 KB Output is correct
6 Correct 34 ms 30756 KB Output is correct
7 Correct 36 ms 30764 KB Output is correct
8 Correct 113 ms 42916 KB Output is correct
9 Correct 107 ms 42792 KB Output is correct
10 Correct 33 ms 30756 KB Output is correct
11 Correct 41 ms 32420 KB Output is correct
12 Correct 39 ms 32500 KB Output is correct
13 Correct 34 ms 30884 KB Output is correct
14 Correct 23 ms 23680 KB Output is correct
15 Incorrect 40 ms 34860 KB Output isn't correct
16 Halted 0 ms 0 KB -