제출 #266939

#제출 시각아이디문제언어결과실행 시간메모리
266939amiratouPaint By Numbers (IOI16_paint)C++14
100 / 100
1358 ms405640 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; const int MOD = (int)1e9+7; const int MAXN=(int)2e5+3,MAXK=103; typedef long long ll; ll dp[MAXN][MAXK],dp2[MAXN][MAXK]; int cnt[MAXN],ans[MAXN][MAXK]; string ANS; void mod(int& a){ if(a>=MOD)a%=MOD; } void mody(ll& a){ if(a>=MOD)a%=MOD; } string solve_puzzle(string s, vector<int> c) { int n=(int)s.size(),k=(int)c.size(); for (int i = 1; i <= n; ++i) { if(s[i-1]=='_')cnt[i]++; cnt[i]+=cnt[i-1]; } dp[n+1][k+1]=dp2[0][0]=1; for (int i = n; i >= 1; i--){ for (int j = 1; j <= k; ++j){ if((i+c[j-1])<=(n+1) && ((i+c[j-1])==(n+1) || s[i+c[j-1]-1]!='X') && (i==1||(s[i-2]!='X')) && !(cnt[i+c[j-1]-1]-cnt[i-1])){ if((i+c[j-1])==(n+1))dp[i][j]+=dp[i+c[j-1]][j+1],mody(dp[i][j]); else dp[i][j]+=dp[i+c[j-1]+1][j+1],mody(dp[i][j]); } if(s[i-1]!='X')dp[i][j]+=dp[i+1][j],mody(dp[i][j]); } if(s[i-1]!='X')dp[i][k+1]+=dp[i+1][k+1],mody(dp[i][k+1]); } for (int i = 1; i <= n; ++i){ for (int j = 1; j <= k; ++j){ if((i-c[j-1])>=0 && (!(i-c[j-1]) || s[i-c[j-1]-1]!='X') && (i==n||(s[i]!='X')) && !(cnt[i]-cnt[i-c[j-1]])){ if(!(i-c[j-1]))dp2[i][j]+=dp2[i-c[j-1]][j-1],mody(dp2[i][j]); else dp2[i][j]+=dp2[i-c[j-1]-1][j-1],mody(dp2[i][j]); } if(s[i-1]!='X')dp2[i][j]+=dp2[i-1][j],mody(dp2[i][j]); } if(s[i-1]!='X')dp2[i][0]+=dp2[i-1][0],mody(dp2[i][0]); } for (int i = 1; i <= n; ++i) for (int j = 1; j <= k; ++j){ if((i+c[j-1])<=(n+1) && ((i==1)||s[i-2]!='X') && ((i+c[j-1])==(n+1) || s[i+c[j-1]-1]!='X') && !(cnt[i+c[j-1]-1]-cnt[i-1])) ans[i][j]=(dp[min(n+1,i+c[j-1]+1)][j+1]*dp2[max(0,i-2)][j-1])%MOD; ans[i][j]+=ans[i-1][j],mod(ans[i][j]); } for (int i = 1; i <= n; ++i){ if(s[i-1]!='.')ANS.push_back(s[i-1]); else{ int f=0,f2=0; for (int j = 1; j <= k; ++j){ f+=(ans[i][j]-ans[max(1,i-c[j-1]+1)-1][j]+MOD)%MOD; f2+=(dp[i+1][j]*dp2[i-1][j-1])%MOD; mod(f),mod(f2); } f2+=(dp[i+1][k+1]*dp2[i-1][k])%MOD,mod(f2); if(f==dp[1][1])ANS.push_back('X'); else if(f2==dp[1][1])ANS.push_back('_'); else ANS.push_back('?'); } } return ANS; }
#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...