Submission #19000831


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define FORR2(x,y,arr) for(auto& [x,y]:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
template<class T> bool chmax(T &a, const T &b) { if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a, const T &b) { if(a>b){a=b;return 1;}return 0;}
//-------------------------------------------------------

int N;
string S;
const ll mo=998244353;

ll C[1<<21][22];
int last=0;

template<class V, int ME> class BIT_mod {
public:
	V bit[1<<ME];
	BIT_mod(){ZERO(bit);};
	V operator()(int e) {ll s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s%mo;}
	void add(int e,V v) { e++; while(e<=1<<ME) { bit[e-1]+=v; bit[e-1] -= (bit[e-1]>=mo)?mo:0; e+=e&-e;}}
};
BIT_mod<int,22> bt[22];


void solve() {
	int i,j,k,l,r,x,y; string s;
	string T;
	
	cin>>S;
	ll pat=1;
	FORR(c,S) if(c=='?') pat=pat*2%mo;
	int NB=0;
	FORR(c,S) if(c=='B') NB++;
	if(NB>=21) {
		cout<<pat<<endl;
		return;
	}
	T="B"+string((1<<20)+1,'S')+S;
	N=T.size();
	
	FOR(i,22) {
		C[0][i]=1;
		bt[i].add(0,1);
	}
	for(i=1;i<N;i++) {
		if(T[i]=='B'||T[i]=='?') {
			for(j=1;j<=21;j++) {
				x=i-(1<<(j-1))-1;
				if(x>=last) {
					C[i][j-1]=(bt[j](x)-bt[j](last-1)+mo)%mo;
					bt[j-1].add(i,C[i][j-1]);
				}
			}
			if(T[i]=='B') last=i;
		}
	}
	ll ret=0;
	for(i=last;i<N;i++) (ret+=C[i][0])%=mo;
	
	cout<<(pat-ret+mo)%mo<<endl;
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}

Submission Info

Submission Time
Task C - Block Game
User kmjp
Language C++ (GCC 9.2.1)
Score 1000
Code Size 1869 Byte
Status AC
Exec Time 2065 ms
Memory 538664 KB

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:34:10: warning: unused variable ‘k’ [-Wunused-variable]
   34 |  int i,j,k,l,r,x,y; string s;
      |          ^
./Main.cpp:34:12: warning: unused variable ‘l’ [-Wunused-variable]
   34 |  int i,j,k,l,r,x,y; string s;
      |            ^
./Main.cpp:34:14: warning: unused variable ‘r’ [-Wunused-variable]
   34 |  int i,j,k,l,r,x,y; string s;
      |              ^
./Main.cpp:34:18: warning: unused variable ‘y’ [-Wunused-variable]
   34 |  int i,j,k,l,r,x,y; string s;
      |                  ^
./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:6:28: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    6 | #define FOR(x,to) for(x=0;x<(to);x++)
      |                            ^
./Main.cpp:78:38: note: in expansion of macro ‘FOR’
   78 |  FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
      |                                      ^~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 2
AC × 22
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt AC 2065 ms 538408 KB
001.txt AC 1907 ms 538576 KB
002.txt AC 310 ms 366752 KB
003.txt AC 218 ms 364668 KB
004.txt AC 1173 ms 538664 KB
005.txt AC 1134 ms 538644 KB
006.txt AC 1119 ms 538660 KB
007.txt AC 1112 ms 538580 KB
008.txt AC 1144 ms 538608 KB
009.txt AC 221 ms 364604 KB
010.txt AC 629 ms 443880 KB
011.txt AC 245 ms 369316 KB
012.txt AC 681 ms 460060 KB
013.txt AC 1065 ms 531008 KB
014.txt AC 983 ms 519264 KB
015.txt AC 1087 ms 538540 KB
016.txt AC 1115 ms 538396 KB
017.txt AC 1057 ms 538444 KB
018.txt AC 1087 ms 538412 KB
019.txt AC 1078 ms 538452 KB
example0.txt AC 222 ms 365532 KB
example1.txt AC 218 ms 365512 KB