QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#270917#2927. Bracket PairingPetroTarnavskyi#AC ✓9ms3876kbC++201.5kb2023-12-01 17:51:422023-12-01 17:51:43

Judging History

This is the latest submission verdict.

  • [2023-12-01 17:51:43]
  • Judged
  • Verdict: AC
  • Time: 9ms
  • Memory: 3876kb
  • [2023-12-01 17:51:42]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	string s;
	cin >> s;
	int n = SZ(s) / 2;
	LL ans = 0;
	FOR(mask, 0, 1 << (2 * n))
	{
		if (__builtin_popcount(mask) != n)
			continue;
		stack<int> st;
		bool ok = true;
		LL cur = 1;
		FOR(i, 0, 2 * n)
		{
			if ((mask >> i) & 1)
			{
				st.push(i);
			}
			else
			{
				if (st.empty())
				{
					ok = false;
					break;
				}
				int j = st.top();
				st.pop();
				int tj, ti;
				if (s[j] == '(')
					tj = 0;
				else if (s[j] == '[')
					tj = 1;
				else if (s[j] == '{')
					tj = 2;
				else if (s[j] == '<')
					tj = 3;
				else if (s[j] == '?')
					tj = 4;
				else
					tj = -1;
				if (s[i] == ')')
					ti = 0;
				else if (s[i] == ']')
					ti = 1;
				else if (s[i] == '}')
					ti = 2;
				else if (s[i] == '>')
					ti = 3;
				else if (s[i] == '?')
					ti = 4;
				else
					ti = -1;
				ok &= tj != -1 && ti != -1 && (tj == ti || tj == 4 || ti == 4);
				if (tj == 4 && ti == 4)
					cur *= 4;
			}
			if (!ok)
				break;
		}
		if (!ok)
			continue;
		ans += cur;
	}
	cout << ans << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3524kb

input:

??

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

????

output:

32

result:

ok single line: '32'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

????????

output:

3584

result:

ok single line: '3584'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

]????]

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

?????[

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

([???]

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

??({?]

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

??({?]??

output:

4

result:

ok single line: '4'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

?[()?)()]]

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

?()?????

output:

320

result:

ok single line: '320'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

?????()?

output:

320

result:

ok single line: '320'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3704kb

input:

???([]){}???

output:

320

result:

ok single line: '320'

Test #13:

score: 0
Accepted
time: 6ms
memory: 3836kb

input:

????????????????????

output:

17611882496

result:

ok single line: '17611882496'

Test #14:

score: 0
Accepted
time: 6ms
memory: 3636kb

input:

<{[{()}]}<>{}>{?()[]

output:

1

result:

ok single line: '1'

Test #15:

score: 0
Accepted
time: 7ms
memory: 3868kb

input:

[<{}<><?[]>?[]{}<{}>

output:

1

result:

ok single line: '1'

Test #16:

score: 0
Accepted
time: 7ms
memory: 3580kb

input:

()<{}{}><???[]>>[()]

output:

9

result:

ok single line: '9'

Test #17:

score: 0
Accepted
time: 6ms
memory: 3644kb

input:

([{?}}<??){<>}[?}<>]

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 7ms
memory: 3644kb

input:

{}(?(?()[]??]<>){[]?

output:

21

result:

ok single line: '21'

Test #19:

score: 0
Accepted
time: 7ms
memory: 3876kb

input:

<??>]??{{}[]}>>()?{}

output:

1

result:

ok single line: '1'

Test #20:

score: 0
Accepted
time: 7ms
memory: 3876kb

input:

{???{(({?><>?>})){}}

output:

8

result:

ok single line: '8'

Test #21:

score: 0
Accepted
time: 6ms
memory: 3584kb

input:

?<()[]?<{?>??>>())[]

output:

11

result:

ok single line: '11'

Test #22:

score: 0
Accepted
time: 6ms
memory: 3804kb

input:

?[()?)()][]{[?}>?]{?

output:

1

result:

ok single line: '1'

Test #23:

score: 0
Accepted
time: 7ms
memory: 3528kb

input:

{?(?>)<>>{}<?{}}?]{?

output:

1

result:

ok single line: '1'

Test #24:

score: 0
Accepted
time: 7ms
memory: 3872kb

input:

[?}[[???[??????]??>?

output:

34880

result:

ok single line: '34880'

Test #25:

score: 0
Accepted
time: 8ms
memory: 3640kb

input:

??<???????<>??[??]{?

output:

629760

result:

ok single line: '629760'

Test #26:

score: 0
Accepted
time: 8ms
memory: 3844kb

input:

?????????[?)?}?>[???

output:

889856

result:

ok single line: '889856'

Test #27:

score: 0
Accepted
time: 9ms
memory: 3648kb

input:

????????????}(??????

output:

275382272

result:

ok single line: '275382272'

Test #28:

score: 0
Accepted
time: 7ms
memory: 3872kb

input:

?[??]?{??)??????????

output:

8609792

result:

ok single line: '8609792'

Test #29:

score: 0
Accepted
time: 8ms
memory: 3636kb

input:

???????(??)??{?????>

output:

16621568

result:

ok single line: '16621568'

Test #30:

score: 0
Accepted
time: 7ms
memory: 3580kb

input:

????[]?[<???????????

output:

21446656

result:

ok single line: '21446656'

Test #31:

score: 0
Accepted
time: 6ms
memory: 3872kb

input:

???????}>??????)?)??

output:

4677632

result:

ok single line: '4677632'

Test #32:

score: 0
Accepted
time: 8ms
memory: 3844kb

input:

[??????(??????????{}

output:

41435136

result:

ok single line: '41435136'

Test #33:

score: 0
Accepted
time: 7ms
memory: 3636kb

input:

(?>?[???????????}???

output:

8740864

result:

ok single line: '8740864'

Test #34:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

()()(?

output:

1

result:

ok single line: '1'

Test #35:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

(??)

output:

5

result:

ok single line: '5'

Test #36:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

(<{}>??]

output:

1

result:

ok single line: '1'

Test #37:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

(?]]

output:

0

result:

ok single line: '0'