제출 #553756

#제출 시각아이디문제언어결과실행 시간메모리
553756AbdelmagedNourLinear Garden (IOI08_linear_garden)C++17
71 / 100
10 ms5416 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; const int MAX=1000005; int pw[MAX],mod; int add(int a,int b){ return a+b-(a+b>=mod?mod:0); } void calc(int N){ pw[0]=1; for(int n=1;n<=N;n++)pw[n]=add(pw[n-1],pw[n-1]); } int solve1(int n,int d){ d++; return pw[(n+(!d))>>1]; } int solve2(int n,int d){ return pw[(n+(!d))>>1]; } int solve3(int n,int d){ d=-d; return pw[(n+(!d))>>1]; } int index(string&s){ int mn=0,mx=0,d=0,res=0,n=s.size(); for(int i=0;i<n;i++){ if(s[i]=='L'){ mn=min(mn,d-1); d--; }else{ int x=0; if(mx<=1&&min(mn,d-1)>=-1)res=add(res,solve1(n-i-1,d-1)),x++; if(mx<=2&&min(mn,d-1)>=0)res=add(res,solve2(n-i-1,d-1)),x++; if(mx<=0&&min(mn,d-1)>=-2)res=add(res,solve3(n-i-1,d-1)),x++; if(x>1)res=add(res,mod-1); mx=max(mx,d+1); d++; } } return add(res,1); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; string s; cin>>n>>mod>>s; calc(n); cout<<index(s); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...