Submission #401327

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

paint

#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
string solve_puzzle(string s,vector<int> c){
    string res=s;
    int n=s.size();
    int k=c.size();
    int pref[n];
    int suf[n];
    int E[n+2];memset(E,0,sizeof(E));
    int P[n+2];
    int ind=0;
    P[0]=0;
    for(int i=0;i<n;i++){
        if(i)P[i]=P[i-1];
        if(s[i]=='_')P[i]++;
    }
    for(int i=0;i<n;i++){
        if(s[i]=='_'){
            P[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;
        while(1){
            if(s[i]=='-')break;
            cant++;
            if(cant==c[ind]){
                suf[ind]=i-1;
                ind--;
                i--;
                break;
            }
            i--;
        }
    }
    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 sum=P[i+c[l]-1];
            if(i)sum-=P[i-1];
            if(sum==0){
                E[i]++;
                E[i+c[l]]--;
            }
        }
    }
    int acum=0;
    return res;
    for(int i=0;i<n;i++){
        acum+=E[i];
        if(acum==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:59:18: warning: unused variable 'ok' [-Wunused-variable]
   59 |             bool ok=true;
      |                  ^~

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