Submission #401336

#	Time	Username	Problem	Language	Result	Execution time	Memory
401336		Pichon5	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	236 KiB

paint

#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)

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;
      |                  ^~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10