Submission #100698

#	Time	Username	Problem	Language	Result	Execution time	Memory
100698		JPN20	Security Gate (JOI18_security_gate)	C++17	30 / 100	852 ms	540 KiB

securitygate

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

int dep[109], N;

bool check(string V) {
	int depth = 0;
	for (int i = 0; i < V.size(); i++) {
		if (V[i] == '(') depth++;
		if (V[i] == ')') depth--;
		if (depth < 0) return false;
	}
	if (depth != 0) return false;
	return true;
}

bool isvalid(string V) {
	// 反転位置は実は一通りに定まる
	dep[0] = 0;
	for (int i = 0; i < V.size(); i++) {
		if (V[i] == '(') dep[i + 1] = dep[i] + 1;
		if (V[i] == ')') dep[i + 1] = dep[i] - 1;
	}
	
	int cl = 0, cr = N;
	for (int i = 0; i <= V.size(); i++) { if (dep[i] < 0) break; cl = i; }
	for (int i = V.size(); i >= 0; i--) { if (dep[i] < dep[V.size()]) break; cr = i; }
	
	if (cl == N && cr == 0) {
		// 両方全部の場合
		return true;
	}
	
	if (cl == N) {
		// 左側だけ全部の場合
		int sabun = dep[V.size()] / 2;
		int mr = -10000;
		for (int i = cr; i <= N; i++) mr = max(mr, dep[i]);
		
		int pr = 10000; for (int i = N; i >= cr; i--) { if (dep[i] == mr) pr = i; }
		int pl = -1; for (int i = 0; i <= pr; i++) { if (dep[i] == mr - sabun) pl = i; }
		if (pl == -1 || pr == -1) return false;
		
		string V1 = V;
		for (int i = pl; i < pr; i++) {
			if (V1[i] == '(') V1[i] = ')';
			else V1[i] = '(';
		}
		return check(V1);
	}
	if (cr == 0) {
		// 右側だけ全部の場合
		int sabun = dep[V.size()] / 2;
		int ml = -10000;
		for (int i = 0; i <= cl; i++) ml = max(ml, dep[i]);
		
		int pl = -1; for (int i = 0; i <= cl; i++) { if (dep[i] == ml) pl = i; }
		int pr = -1; for (int i = N; i >= pl; i--) { if (dep[i] == ml + sabun) pr = i; }
		if (pl == -1 || pr == -1) return false;
		
		string V1 = V;
		for (int i = pl; i < pr; i++) {
			if (V1[i] == '(') V1[i] = ')';
			else V1[i] = '(';
		}
		return check(V1);
	}
	
	// 共通部分がない場合
	int sabun = dep[V.size()] / 2;
	int ml = -10000, mr = -10000;
	for (int i = 0; i <= cl; i++) ml = max(ml, dep[i]);
	for (int i = cr; i <= N; i++) mr = max(mr, dep[i]);
	
	int s = min(ml, mr - sabun);
	int pl = -1; for (int i = 0; i <= cl; i++) { if (dep[i] == s) pl = i; }
	int pr = -1; for (int i = N; i >= cr; i--) { if (dep[i] == s + sabun) pr = i; }
	if (pl == -1 || pr == -1) return false;
	
	string V1 = V;
	for (int i = pl; i < pr; i++) {
		if (V1[i] == '(') V1[i] = ')';
		else V1[i] = '(';
	}
	return check(V1);
}

string S;

int main(){
	cin >> N >> S; vector<int>vec;
	if (N % 2 == 1) { cout << "0" << endl; return 0; }
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == 'x') vec.push_back(i);
	}
	
	int cnt = 0;
	
	for (int i = 0; i < (1 << vec.size()); i++) {
		string T = S;
		for (int j = 0; j < vec.size(); j++) {
			if ((i & (1 << j)) != 0) T[vec[j]] = ')';
			else T[vec[j]] = '(';
		}
		
		bool I = isvalid(T);
		if (I == true) cnt++;
	}
	cout << cnt << endl;
	return 0;
}

Compilation message (stderr)

securitygate.cpp: In function 'bool check(std::__cxx11::string)':
securitygate.cpp:8:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) {
                  ~~^~~~~~~~~~
securitygate.cpp: In function 'bool isvalid(std::__cxx11::string)':
securitygate.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) {
                  ~~^~~~~~~~~~
securitygate.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= V.size(); i++) { if (dep[i] < 0) break; cl = i; }
                  ~~^~~~~~~~~~~
securitygate.cpp: In function 'int main()':
securitygate.cpp:93:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~
securitygate.cpp:101:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < vec.size(); j++) {
                   ~~^~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 0 / 43
• Subtask 5: 0 / 27