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 |
|
|
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 |