Submission #401332

#TimeUsernameProblemLanguageResultExecution timeMemory
401332Pichon5Paint By Numbers (IOI16_paint)C++17
32 / 100
2078 ms256 KiB
#include "paint.h" #include <bits/stdc++.h> #include <cstdlib> #define vi vector<int> using namespace std; string solve_puzzle(string s,vector<int> c){ string res=s; vi pref,suf; int n=s.size(); int k=c.size(); pref.resize(n+1);suf.resize(n+1); int ind=0; vi E(n+1,0); vi P(n+1); for(int i=0;i<n;i++){ P[i]=0; if(s[i]=='_')P[i]=1; if(i)P[i]+=P[i-1]; } for(int i=0;i<n;i++){ if(s[i]=='_')continue; int cant=0; if(ind==k)break; while(i<n){ if(s[i]=='-')break; cant++; if(cant==c[ind]){ pref[ind]=i+1; ind++; i++; break; } i++; } } ind=k;ind--; for(int i=n-1;i>=0;i--){ if(s[i]=='-')continue; int cant=0; if(ind==-1)break; while(1){ if(s[i]=='-')break; cant++; if(cant==c[ind]){ suf[ind]=i-1; ind--; i--; break; } i--; } } vector<bool>check(n+1,false); for(int i=0;i<n;i++){ if(s[i]=='_')continue; for(int l=0;l<k;l++){ if((l && pref[l-1]>=i)or(i+c[l]-1>n))continue; if((l+1<k && suf[l+1]<=i+c[l]-1) or(i+c[l]-1>n))continue; bool ok=true; int S=P[i+c[l]-1]; if(i)S-=P[i-1]; if(S==0){ E[i]++; E[i+c[l]]--; } } } int aux=0; for(int i=0;i<n;i++){ aux+=E[i]; if(aux==0){ res[i]='_'; s[i]='_'; }else{ res[i]='?'; } } for(int i=0;i<k;i++){ int b=0,e=n-1; if(i)b=pref[i-1]+1; if(i+1<k)e=suf[i+1]-1; int R=0,l=b,L=0,cant=0; while(1){ if(s[l]=='_'){ cant=0; continue; } cant++; if(cant==c[i]){ R=l; break; } l++; } l=e; cant=0; while(1){ if(s[l]=='-'){ cant=0; continue; } cant++; if(cant==c[i]){ L=l; break; } l--; } for(l=L;l<=R;l++){ res[l]='X'; } } return res; }

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:60:18: warning: unused variable 'ok' [-Wunused-variable]
   60 |             bool ok=true;
      |                  ^~
#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...