oj.uz

Submission #148577

# Submission time Handle Problem Language Result Execution time Memory
148577 2019-09-01T04:41:58 Z 본인 하지만 안 어림 ㅋㅋ(#3569, gs13105, xdoju, gs13068) HicCup (FXCUP4_hiccup) C++17
0 / 100
 5 ms 384 KB 
#include <bits/stdc++.h>
using namespace std; 

#include "hiccup.h"

int HicCup(std::string s) {

    s.insert(s.begin(), 'H');
    s.push_back('C');

	int n = s.size();

    int c = 0;
    for(int i = 0; i < n; i++)
    {
        if(s[i] == 'H')
            c++;
        else if(s[i] == 'C')
            c--;

        if(c < 0)
            return -1;
    }
    if(c != 0)
        return -1;

    int l = 0;
    int r = n;
    while(l <= r)
    {
        int x = (l + r + 1) / 2;

        bool ok = 1;
        bool u = 0;
        int t = 0;
        stack<vector<int>> stk;
        stk.push(vector<int>());
        for(int i = 0; i < n; i++)
        {
            if(s[i] == 'H')
            {
                if(i != 0)
                {
                    stk.top().push_back(t);
                    t = 0;
                }

                stk.push(vector<int>());
                u = 0;
            }
            else if(s[i] == 'C')
            {
                stk.top().push_back(t);
                t = 0;

                assert(stk.top()[0] == 0);

                int sz = stk.top().size();
                int cnt = 0;
                for(int j = sz - 1; j >= 1; j--)
                {
                    cnt += stk.top()[j];
                    cnt -= x;
                    if(cnt < 0)
                    {
                        ok = 0;
                        break;
                    }
                }
                if(!ok)
                    break;

                stk.pop();

                u = 1;
            }
            else
            {
                if(!u)
                    return -1;
                t++;
            }
        }

        if(l == r)
        {
            assert(ok);

            assert(l == 0);

            return l;
        }

        if(ok)
            l = x;
        else
            r = x - 1;
    }
}

Compilation message

hiccup.cpp: In function 'int HicCup(std::__cxx11::string)':
hiccup.cpp:99:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 128 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 76.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 128 KB Output isn't correct
3 Halted 0 ms 0 KB -