Submission #882514

#	Time	Username	Problem	Language	Result	Execution time	Memory
882514		JakobZorz	Paint By Numbers (IOI16_paint)	C++14	7 / 100	1 ms	436 KiB

paint

#include"paint.h"
#include<cstdlib>
#include<iostream>
using namespace std;

string str;
vector<int>arr;
int n,m;
bool can_white[200000];
bool can_black[200000];

bool is_possible(int i,int j);

bool is_possible_directly(int i,int j){
    if(j==m)
        return false;
    
    if(i+arr[j]>n)
        return false;
    
    for(int k=i;k<i+arr[j];k++)
        if(str[k]=='_')
            return false;
    
    if(j!=m-1){
        if(i+arr[j]>=n)
            return false;
        if(str[i+arr[j]]=='X')
            return false;
        return is_possible(i+arr[j]+1,j+1);
    }
    
    return is_possible(i+arr[j],j+1);
}

bool is_possible(int i,int j){
    if(i==n)
        return j==m;
    
    if(str[i]=='_')
        return is_possible(i+1,j);
    
    bool nxt=is_possible_directly(i,j);
    if(str[i]=='X')
        return nxt;
    
    return nxt||is_possible(i+1,j);
}

void recurse(int i,int j){
    if(!is_possible(i,j))
        return;
    if(i==n)
        return;
    
    if(is_possible_directly(i,j)){
        for(int k=i;k<i+arr[j];k++)
            can_white[k]=true;
        
        if(j==m-1){
            can_black[i+arr[j]]=true;
            recurse(i+arr[j],j+1);
        }else
            recurse(i+arr[j]+1,j+1);
    }
    
    if(is_possible(i+1,j)){
        can_black[i]=true;
        recurse(i+1,j);
    }
}

string solve_puzzle(string s,vector<int>c){
    str=s;
    arr=c;
    n=(int)s.size();
    m=(int)c.size();
    
    recurse(0,0);
    
    string res;
    res.resize(n);
    for(int i=0;i<n;i++){
        if(can_white[i]&&can_black[i])
            res[i]='?';
        else if(can_white[i])
            res[i]='X';
        else
            res[i]='_';
    }
    return res;
}

• Subtask 1: 7 / 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