Submission #401318

#	Time	Username	Problem	Language	Result	Execution time	Memory
401318		Pichon5	Paint By Numbers (IOI16_paint)	C++17	32 / 100	2081 ms	304 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);
    //prefi hasta donde pongo los primero ci
    //suf hasta donde pongo ci,ci+1,.....ck
    int ind=0;
    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;
            for(int j=i;j<=i+c[l]-1;j++){
                if(s[j]=='_')ok=false;
            }
            //cout<<l<<"  "<<i<<endl;
            if(ok){
                for(int j=i;j<=i+c[l]-1;j++){
                    check[j]=true;
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        if(check[i]==false){
            res[i]='_';
            s[i]='_';
        }else{
            res[i]='?';
        }
    }
    //cout<<"  "<<res<<endl;
    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--;
        }
        //cout<<i<<"  "<<R<<"  "<<L<<endl;
        for(l=L;l<=R;l++){
            res[l]='X';
        }
        //out<<i<<"  "<<R<<"  y  "<<L<<endl;
    }
    return res;
}

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