# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
401336 | Pichon5 | Paint By Numbers (IOI16_paint) | C++17 | 1 ms | 236 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
//cout<<b<<" "<<e<<endl;
while(1){
if(s[l]=='_'){
l++;
cant=0;
continue;
}
cant++;
if(cant==c[i]){
R=l;
break;
}
l++;
}
//cout<<"ele "<<R<<endl;
l=e;
cant=0;
while(1){
if(s[l]=='_'){
l--;
cant=0;
continue;
}
cant++;
if(cant==c[i]){
L=l;
break;
}
l--;
}
//cout<<R<<" "<<L<<endl;
for(l=L;l<=R;l++){
res[l]='X';
}
}
return res;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |