제출 #1023056

#제출 시각아이디문제언어결과실행 시간메모리
1023056amirhoseinfar1385Paint By Numbers (IOI16_paint)C++17
59 / 100
1 ms772 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(j>0&&s[i-c[j-1]-1]=='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(j<k&&s[i+c[j-1]-1]=='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; } 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){ hey[i]++; hey[i-c[j-1]]--; } } } for(int i=n;i>=0;i--){ hey[i]+=hey[i+1]; //cout<<"chemighy: "<<i<<" "<<hey[i]<<" "<<vas[i]<<endl; if(hey[i]!=0){ //cout<<i<<" "<<vas[i]<<endl; 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]==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...