Submission #882535

#	Time	Username	Problem	Language	Result	Execution time	Memory
882535		JakobZorz	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1417 ms	131012 KiB

paint

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

string str;
vector<int>arr;
int n,m;
int can_white[200001];
bool can_black[200000];
int next_[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(next_[i]<i+arr[j])
        return false;
    
    if(j==m-1){
        dp1[i][j]=is_possible(i+arr[j],j+1);
        return dp1[i][j];
    }
    
    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];
}

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)){
        can_white[i]++;
        can_white[i+arr[j]]--;
        
        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)&&str[i]!='X'){
        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();
    
    int curr_=n;
    for(int i=n-1;i>=0;i--){
        if(str[i]=='_')
            curr_=i;
        next_[i]=curr_;
    }
    
    recurse(0,0);
    
    string res;
    res.resize(n);
    int white=0;
    for(int i=0;i<n;i++){
        white+=can_white[i];
        if(white&&can_black[i])
            res[i]='?';
        else if(white)
            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: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10