Submission #1856883
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) { for (char *pnt = &S[l]; pnt <= &S[m]; ++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) { for (char *pnt = &S[r]; pnt >= &S[m]; --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 | D - Parenthesis Sequence |
User | yocchiman |
Language | C++ (Clang 3.8.0) |
Score | 0 |
Code Size | 3054 Byte |
Status | WA |
Exec Time | 2103 ms |
Memory | 1792 KB |
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 |
All | sample_01.txt, sample_02.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, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
test_01.txt | AC | 19 ms | 1664 KB |
test_02.txt | AC | 19 ms | 1664 KB |
test_03.txt | AC | 19 ms | 1664 KB |
test_04.txt | AC | 1660 ms | 1792 KB |
test_05.txt | AC | 24 ms | 1792 KB |
test_06.txt | TLE | 2103 ms | 1408 KB |
test_07.txt | TLE | 2103 ms | 1408 KB |
test_08.txt | TLE | 2103 ms | 1408 KB |
test_09.txt | WA | 1693 ms | 1792 KB |
test_10.txt | WA | 1633 ms | 1792 KB |
test_11.txt | WA | 1088 ms | 1792 KB |
test_12.txt | WA | 987 ms | 1792 KB |
test_13.txt | WA | 734 ms | 1792 KB |
test_14.txt | WA | 718 ms | 1792 KB |
test_15.txt | WA | 770 ms | 1792 KB |
test_16.txt | WA | 754 ms | 1792 KB |
test_17.txt | WA | 1152 ms | 1792 KB |
test_18.txt | WA | 1156 ms | 1792 KB |
test_19.txt | WA | 1970 ms | 1792 KB |
test_20.txt | WA | 1971 ms | 1792 KB |
test_21.txt | TLE | 2103 ms | 1408 KB |
test_22.txt | TLE | 2103 ms | 1280 KB |
test_23.txt | TLE | 2103 ms | 1280 KB |
test_24.txt | TLE | 2103 ms | 1280 KB |
test_25.txt | TLE | 2103 ms | 1408 KB |
test_26.txt | TLE | 2103 ms | 1280 KB |
test_27.txt | TLE | 2103 ms | 1280 KB |