제출 #1023096

#제출 시각아이디문제언어결과실행 시간메모리
1023096amirhoseinfar1385Paint By Numbers (IOI16_paint)C++17
100 / 100
313 ms317652 KiB
#include "paint.h" #include<bits/stdc++.h> using namespace std; const int maxn=200000+10,maxk=200; int n,k,dpps[maxn][maxk],dpsuf[maxn][maxk],vas[maxn],ted1[maxn],ted2[maxn],hey[maxn]; std::string solve_puzzle(std::string s, std::vector<int> c) { n=(int)s.size(); k=(int)c.size(); s.push_back('.'); for(int i=1;i<=n;i++){ ted1[i]+=ted1[i-1]; ted2[i]+=ted2[i-1]; ted1[i]+=(s[i-1]=='X'); ted2[i]+=(s[i-1]=='_'); } dpps[0][0]=1; dpsuf[n+1][k+1]=dpsuf[n+2][k+1]=1; for(int i=1;i<=n;i++){ if(s[i-1]!='X'){ dpps[i][0]|=dpps[i-1][0]; } for(int j=1;j<=k;j++){ if(s[i-1]!='X'){ dpps[i][j]|=dpps[i-1][j]; } if(i>=c[j-1]+(j>1)&&ted2[i]-ted2[i-c[j-1]]==0){ if(i-c[j-1]-1>=0&&s[i-c[j-1]-1]=='X'){ continue; } if(s[i]=='X'){ continue; } dpps[i][j]|=dpps[i-c[j-1]-(j>1)][j-1]; } } } for(int i=n;i>=1;i--){ if(s[i-1]!='X'){ dpsuf[i][k+1]|=dpsuf[i+1][k+1]; } for(int j=k;j>=1;j--){ if(s[i-1]!='X'){ dpsuf[i][j]|=dpsuf[i+1][j]; } if(i+c[j-1]+(j<k)-1<=n&&ted2[i+c[j-1]-1]-ted2[i-1]==0){ if(s[i+c[j-1]-1]=='X'){ continue; } if(i>1&&s[i-2]=='X'){ continue; } dpsuf[i][j]|=dpsuf[i+c[j-1]+(j<k)][j+1]; } } } for(int i=1;i<=n;i++){ for(int j=0;j<=k;j++){ if(dpps[i-1][j]==1&&dpsuf[i+1][j+1]==1){ vas[i]=1; } //cout<<i<<" "<<j<<" "<<dpps[i][j]<<" "<<dpsuf[i][j]<<endl; if(dpps[i][j]==1&&dpsuf[i+2][j+1]==1&&j>0&&dpps[i-c[j-1]-(j>1)][j-1]==1&&ted2[i]-ted2[i-c[j-1]]==0&&s[i]!='X'){ if(i-c[j-1]-1>=0&&s[i-c[j-1]-1]=='X'){ continue; } hey[i]++; hey[i-c[j-1]]--; } } } for(int i=n;i>=0;i--){ hey[i]+=hey[i+1]; if(hey[i]!=0){ vas[i]+=2; } } string ret; ret.resize(n); for(int i=0;i<n;i++){ if(s[i]=='X'||s[i]=='_'){ ret[i]=s[i]; continue; } if(vas[i+1]==0){ exit(23); } if(vas[i+1]==1){ ret[i]='_'; }else if(vas[i+1]==2){ ret[i]='X'; }else{ ret[i]='?'; } } return ret; }
#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...