Submission #1856926


Source Code Expand

#include <vector>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>
#include <list>
#include <assert.h>
using namespace std;

struct Param
{
    int x;
    int y;
};

struct Question
{
    int l;
    int r;
};

#define MAXN 100001
char S[MAXN];
Question Q[MAXN];
int R[MAXN];

#define PRINT(x) { std::cout << #x << ": " << x << std::endl; }


bool
lpreprocess(int l, int m, Param& p)
{
    char *sm = &S[m];
    for (char *pnt = &S[l]; pnt <= sm; ++pnt)
    {
        switch (*pnt)
        {
            case '(':
                ++p.x;
                break;
            case ')':
                if (p.x == 0)
                {
                    if (p.y == 0) return false;

                    --p.y;
                }
                else
                {
                    --p.x;
                }
                break;
            case '?':
                ++p.y;
                break;
            default:
                PRINT(*pnt);
                assert(false);
                break;
        }
    }
    return true;
}

bool
rpreprocess(int m, int r, Param& p)
{
    char *sm = &S[m];
    for (char *pnt = &S[r]; pnt >= sm; --pnt)
    {
        switch (*pnt)
        {
            case ')':
                ++p.x;
                break;
            case '(':
                if (p.x == 0)
                {
                    if (p.y == 0) return false;

                    --p.y;
                }
                else
                {
                    --p.x;
                }
                break;
            case '?':
                ++p.y;
                break;
            default:
                PRINT(*pnt);
                assert(false);
        }
    }
    return true;
}

bool
validate(int l, int r)
{
    int n = r - l + 1;
    if (n % 2 == 1)
    {
        return false;
    }
    Param lp = {0, 0};
    if (!lpreprocess(l, l + n / 2 - 1, lp))
    {
        return false;
    }
    Param rp = {0, 0};
    if (!rpreprocess(l + n / 2, r, rp))
    {
        return false;
    }
    int v = lp.x + lp.y - rp.x - rp.y;
    // #define PRINT(x) { std::cout << #x << ": " << x << std::endl; }
    // PRINT(v);
    // PRINT(lp.x);
    // PRINT(lp.y);
    // PRINT(rp.x);
    // PRINT(rp.y);
    if (v % 2 == 1)
    {
        return false;
    }
    if (v < -2 * (rp.y / 2) || 2 * (lp.y / 2) < v)
    {
        return false;
    }
    return true;
}


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    scanf("%d", &n);
    scanf("%s", S);
    S[n] = '\0';
    int nq;
    scanf("%d", &nq);
    Question *q;
    for (q = Q; q < &Q[nq]; ++q)
    {
        scanf("%d %d", &q->l, &q->r);
    }
    q = Q;
    for (int *r = R; r < &R[nq]; ++r, ++q)
    {
        *r = validate(q->l - 1, q->r - 1);
    }
    for (int *r = R; r < &R[nq]; ++r)
    {
        cout << (*r ? "Yes\n" : "No\n");
    }
    cout << flush;
}

Submission Info

Submission Time
Task A - MUJIN
User yocchiman
Language C++ (GCC 5.4.1)
Score 0
Code Size 3094 Byte
Status RE
Exec Time 104 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:143:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:144:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", S);
                   ^
./Main.cpp:147:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nq);
                     ^
./Main.cpp:151:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &q->l, &q->r);
                                     ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
RE × 3
RE × 21
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt
Case Name Status Exec Time Memory
sample_01.txt RE 97 ms 256 KB
sample_02.txt RE 96 ms 256 KB
sample_03.txt RE 96 ms 256 KB
test_01.txt RE 96 ms 256 KB
test_02.txt RE 96 ms 256 KB
test_03.txt RE 96 ms 256 KB
test_04.txt RE 96 ms 256 KB
test_05.txt RE 96 ms 256 KB
test_06.txt RE 96 ms 256 KB
test_07.txt RE 104 ms 256 KB
test_08.txt RE 96 ms 256 KB
test_09.txt RE 96 ms 256 KB
test_10.txt RE 96 ms 256 KB
test_11.txt RE 96 ms 256 KB
test_12.txt RE 96 ms 256 KB
test_13.txt RE 96 ms 256 KB
test_14.txt RE 96 ms 256 KB
test_15.txt RE 97 ms 256 KB
test_16.txt RE 99 ms 256 KB
test_17.txt RE 96 ms 256 KB
test_18.txt RE 97 ms 256 KB