Submission #882516

#	Time	Username	Problem	Language	Result	Execution time	Memory
882516		JakobZorz	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	4852 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 dpt1[200001][101];
bool dp1[200001][101];
bool is_possible_directly(int i,int j){
    if(dpt1[i][j])
        return dp1[i][j];
    dpt1[i][j]=true;
    
    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;
        dp1[i][j]=is_possible(i+arr[j]+1,j+1);
        return dp1[i][j];
    }
    
    dp1[i][j]=is_possible(i+arr[j],j+1);
    return dp1[i][j];
}

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

bool vis[200001][201];
void recurse(int i,int j){
    if(vis[i][j])
        return;
    vis[i][j]=true;
    
    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)
            recurse(i+arr[j],j+1);
        else{
            can_black[i+arr[j]]=true;
            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: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10