제출 #208975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
208975		Segtree	Security Gate (JOI18_security_gate)	C++14	30 / 100	971 ms	504 KiB

securitygate

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef unordered_set<ll> uset;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=0;i<=n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")
ll n;
bool solve2(string s){
	for(int L=0;L<n;L++)for(int R=L;R<n;R++){
		bool ok=1;
		ll rui=0;
		rep(i,n){
			rui+=((s[i]=='(')^(L<=i&&i<=R)?+1:-1);
			ok&=(rui>=0);
		}
		ok&=(rui==0);
		if(ok)return 1;
	}
	bool ok=1;
	ll rui=0;
	rep(i,n){
		rui+=((s[i]=='(')?+1:-1);
		ok&=(rui>=0);
	}
	ok&=(rui==0);
	return ok;
}
bool solve(string s){
	int rui;
	{//終わりが正になるようにreverse
		rui=0;
		rep(i,n)rui+=(s[i]=='('?+1:-1);
		if(rui<0){
			reverse(all(s));
			rep(i,n){
				if(s[i]=='(')s[i]=')';
				else s[i]='(';
			}
		}
	}
	int L=n,R=-1;//左右から見て、はじめて累積和が負になる点
	{//L,Rを求める
		rui=0;
		for(int i=n-1;i>=0;i--){
			rui+=(s[i]==')'?+1:-1);
			if(rui<0)chmax(R,i);
		}
		rui=0;
		rep(i,n){
			rui+=(s[i]=='('?+1:-1);
			if(rui<0)chmin(L,i);
		}
	}
	int d;
	{//終わりの値を求めてdに代入する
		rui=0;
		rep(i,n)rui+=(s[i]=='('?+1:-1);
		d=rui;
	}
	if(L==n&&R==-1){//どちらから見ても累積和が負にならない
		return 1;
	}
	if(L==n){//左から見ると累積和が負にならないケース
		int b=0,h=0;
		rui=0;
		for(int i=n-1;i>=0;i--){
			rui+=(s[i]==')'?+1:-1);
			if(R+1<=i)chmax(b,rui);
		}
		rui=0;
		for(int i=n-1;i>=0;i--){
			rui+=(s[i]==')'?+1:-1);
			if(rui==b-d/2)break;
			chmax(h,rui);
		}
		return (2*b>=h);
	}
	//どちらから見ても累積和が負になるケース
	int a=0,b=0,h=0;
	if(L==n)a=1e9;
	if(R==-1)b=1e9;
	rui=0;
	rep(i,n){
		rui+=(s[i]=='('?+1:-1);
		if(i<=L-1)chmax(a,rui);
		if(R<=i)chmax(b,rui-d);
		if(L-1<=i&&i<=R)chmax(h,rui-d);
	}
	bool ok=1;
	ok&=h<=2*b;
	ok&=h+d<=2*a;
	return ok;
}

int main(){
	string s;
	cin>>n>>s;
	if(n%2==1){cout<<0<<endl;return 0;}
	vector<ll> X;
	rep(i,n)if(s[i]=='x')X.push_back(i);
	if(X.size()>20)return 0;
	ll ans=0;
	rep(i,(1<<(ll)X.size())){
		rep(j,X.size())s[X[j]]=(i&(1<<j)?'(':')');
		bool res=solve(s);
		/*bool realres=solve2(s);
		if(res!=realres){
			cerr<<s<<" "<<res<<" "<<realres<<endl;
		}*/
		//cout<<s<<" "<<res<<endl;
		ans+=res;
	}	
	cout<<ans<<endl;
}

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

securitygate.cpp:16:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("O3")
 
securitygate.cpp:17:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("unroll-loops")
 
securitygate.cpp:18:0: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
 #pragma gcc target("avx2,see4")
 
securitygate.cpp: In function 'int main()':
securitygate.cpp:11:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n) for(int i=0;i<n;i++)
securitygate.cpp:116:7:
   rep(j,X.size())s[X[j]]=(i&(1<<j)?'(':')');
       ~~~~~~~~~~               
securitygate.cpp:116:3: note: in expansion of macro 'rep'
   rep(j,X.size())s[X[j]]=(i&(1<<j)?'(':')');
   ^~~

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