제출 #62032

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62032		gs14004	parentrises (BOI18_parentrises)	C++17	0 / 100	26 ms	488 KiB

parentrises

#include<bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 1000050;

bool det(string s){
	queue<int> que;
	string chk;
	int cnt = 0;
	chk.resize(s.size());
	for(int i=0; i<s.size(); i++){
		if(s[i] == '('){
			que.push(i);
			cnt++;
			chk[i] = '?';
		}
		else{
			if(cnt > 0){
				chk[i] = '!';
				cnt--;
			}
			else{
				if(que.empty()) return 0;
				int x = que.front();
				que.pop();
				chk[x] = 'G';
				chk[i] = '!';
			}
		}
	}
	for(int i=(int)s.size()-1; i>=0; i--){
		if(s[i] == ')' && cnt){
			chk[i] = 'G';
			cnt--;
		}
	}
	if(cnt > 0) return 0;
	int c0 = 0, c1 = 0;
	for(int i=0; i<s.size(); i++){
		if(s[i] == '('){
			if(chk[i] == 'G') cnt += 2;
			else{
				cnt++;
				if(cnt & 1) chk[i] = 'R';
				else chk[i] = 'B';
			}
			if(chk[i] != 'B') c0++;
			if(chk[i] != 'R') c1++;
		}
		else{
			if(chk[i] == 'G') cnt -= 2;
			else{
				if(cnt & 1) chk[i] = 'R';
				else chk[i] = 'B';
				cnt--;
				if(chk[i] != 'B') c0--;
				if(chk[i] != 'R') c1--;
				if(c0 < 0 || c1 < 0) return 0;
			}
		}
	}
	if(c0 == 0 && c1 == 0) return 1;
	else return 0;
}

int f(int n){
	int ans = 0;
	for(int i=0; i<(1<<n); i++){
		string s;
		for(int j=0; j<n; j++){
			if((i >> j) & 1) s.push_back('(');
			else s.push_back(')');
		}
		if(det(s)) ans++;
	}
	return ans;
}

string solve(string s){
	queue<int> que;
	string chk;
	int cnt = 0;
	chk.resize(s.size());
	for(int i=0; i<s.size(); i++){
		if(s[i] == '('){
			que.push(i);
			cnt++;
			chk[i] = '?';
		}
		else{
			if(cnt > 0){
				chk[i] = '!';
				cnt--;
			}
			else{
				if(que.empty()) return "impossible";
				int x = que.front();
				que.pop();
				chk[x] = 'G';
				chk[i] = '!';
			}
		}
	}
	for(int i=(int)s.size()-1; i>=0; i--){
		if(s[i] == ')' && cnt){
			chk[i] = 'G';
			cnt--;
		}
	}
	if(cnt > 0) return "impossible";
	int c0 = 0, c1 = 0;
	for(int i=0; i<s.size(); i++){
		if(s[i] == '('){
			if(chk[i] == 'G') cnt += 2;
			else{
				cnt++;
				if(cnt & 1) chk[i] = 'R';
				else chk[i] = 'B';
			}
			if(chk[i] != 'B') c0++;
			if(chk[i] != 'R') c1++;
		}
		else{
			if(chk[i] == 'G') cnt -= 2;
			else{
				if(cnt & 1) chk[i] = 'R';
				else chk[i] = 'B';
				cnt--;
				if(chk[i] != 'B') c0--;
				if(chk[i] != 'R') c1--;
				if(c0 < 0 || c1 < 0) return "impossible";
			}
		}
	}
	if(c0 == 0 && c1 == 0) return chk;
	else return "impossible";
}

int main(){
	char buf[MAXN];
	int p, t; cin >> p;
	if(p == 1){
		scanf("%d",&t);
		while(t--){
			scanf("%s",buf);
			string ans = buf;
			printf("%s\n", solve(buf).c_str());
		}
	}
	else{
		scanf("%d",&t);
		while(t--){
			int n; cin >> n;
			cout << f(n) << endl;
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

parentrises.cpp: In function 'bool det(std::__cxx11::string)':
parentrises.cpp:12:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s.size(); i++){
               ~^~~~~~~~~
parentrises.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s.size(); i++){
               ~^~~~~~~~~
parentrises.cpp: In function 'std::__cxx11::string solve(std::__cxx11::string)':
parentrises.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s.size(); i++){
               ~^~~~~~~~~
parentrises.cpp:113:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s.size(); i++){
               ~^~~~~~~~~
parentrises.cpp: In function 'int main()':
parentrises.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
   ~~~~~^~~~~~~~~
parentrises.cpp:146:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s",buf);
    ~~~~~^~~~~~~~~~
parentrises.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
   ~~~~~^~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 6
• Subtask 4: 0 / 28
• Subtask 5: 0 / 6
• Subtask 6: 0 / 16
• Subtask 7: 0 / 28