제출 #285667

#제출 시각아이디문제언어결과실행 시간메모리
285667eohomegrownappsPaint By Numbers (IOI16_paint)C++14
32 / 100
1 ms384 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; vector<int> blocklengths; string requirements; vector<int> prefsumw; vector<int> prefsumb; vector<vector<bool>> dpl; //[numblocks][ind] -- ending on white //1-indexed! vector<vector<bool>> dpr; //0-indexed int n,m; // check whether block within a and b: prefsumw[b+1]-prefsum[a]==0 bool canFill(int a, int b){ return prefsumw[b+1]-prefsumw[a]==0; } bool canEmpty(int a, int b){ return prefsumb[b+1]-prefsumb[a]==0; } inline bool getL(int a, int x){ return dpl[a][x+1]; } inline bool getR(int a, int x){ return dpr[a][x]; } void gendata(){ n = requirements.size(); m = blocklengths.size(); //generate prefix sums prefsumw.resize(n+1); prefsumb.resize(n+1); for (int i = 1; i<=n; i++){ prefsumw[i]=prefsumw[i-1]+(requirements[i-1]=='_'); prefsumb[i]=prefsumb[i-1]+(requirements[i-1]=='X'); } //generate DP dpl.resize(m+1,vector<bool>(n+1,false)); dpl[0][0]=true; for (int a = 0; a<=m; a++){ for (int x = 1; x<=n; x++){ if (requirements[x-1]=='X'){ dpl[a][x]=false; continue; } if (dpl[a][x-1]){ dpl[a][x]=true; continue; } if (x-2>=0&&requirements[x-2]=='W'){ continue; } if (a>0&&x-1-blocklengths[a-1]>=0){ if (dpl[a-1][x-1-blocklengths[a-1]]){ dpl[a][x]=true; continue; } } } } dpr.resize(m+1,vector<bool>(n+1,false)); dpr[0][n]=true; for (int a = 0; a<=m; a++){ for (int x = n-1; x>=0; x--){ if (requirements[x]=='X'){ dpr[a][x]=false; continue; } if (dpr[a][x+1]){ dpr[a][x]=true; continue; } if (x+1<n&&requirements[x+1]=='W'){ continue; } if (a>0&&x+1+blocklengths[m-a]<=n){ if (dpr[a-1][x+1+blocklengths[m-a]]){ dpr[a][x]=true; continue; } } } } /*for (int a = 0; a<=m; a++){ cout<<a<<" blocks to left:\n"; for (int i = 0; i<n; i++){ cout<<getL(a,i)<<' '; }cout<<'\n'; } for (int a = 0; a<=m; a++){ cout<<a<<" blocks to right:\n"; for (int i = 0; i<n; i++){ cout<<getR(a,i)<<' '; }cout<<'\n'; }*/ } std::string solve_puzzle(std::string s, std::vector<int> c) { requirements = s; blocklengths = c; gendata(); vector<int> canUseBlack(n+1,0); // what if a = 0 for (int a = 0; a<m; a++){ for (int x = 0; x+blocklengths[a]<=n; x++){ //can we place block a at x? // possible off by one if (getL(a,x-1)&&getR(m-1-a,x+blocklengths[a])&&canFill(x,x+blocklengths[a]-1)){ canUseBlack[x]++; canUseBlack[x+blocklengths[a]]--; //cout<<"can have block "<<a<<" from "<<x<<" to "<<x+blocklengths[a]-1<<'\n'; } } } for (int i = 1; i<=n; i++){ canUseBlack[i]+=canUseBlack[i-1]; } /*cout<<"can have black:\n"; for (int i = 0; i<n; i++){ cout<<bool(canUseBlack[i]>0)<<' '; }cout<<'\n';*/ vector<bool> canUseWhite(n,false); for (int a = 0; a<=m; a++){ for (int x = 0; x<n; x++){ if (getL(a,x)&&getR(m-a,x)){ canUseWhite[x]=true; } } } /*cout<<"can have white:\n"; for (int i = 0; i<n; i++){ cout<<canUseWhite[i]<<' '; }cout<<'\n';*/ string answer; for (int i = 0; i<n; i++){ if (canUseBlack[i]>0&&canUseWhite[i]){ answer+='?'; } else if (canUseBlack[i]>0){ answer+='X'; } else if (canUseWhite[i]){ answer+='_'; } else { assert(1==0); } } return answer; }
#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...