Submission #138109

#	Time	Username	Problem	Language	Result	Execution time	Memory
138109		Hassoony	Paint By Numbers (IOI16_paint)	C++17	100 / 100	589 ms	99708 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
const int MX=2e5+9;
int Pref[MX],dp[MX][102],c[102],n,k,White[MX],BL[MX];
string s,ans;
int GetSum(int l,int r){
    int Pl=0;
    if(l)Pl=Pref[l-1];
    return Pref[r]-Pl;
}
void add(int l,int r){
    BL[l]++;BL[r+1]--;
}
int DP(int x,int y){
    if(x>=n){
        if(y != k)return 0;
        return 1;
    }
    int &ret=dp[x][y];if(ret!=-1)return ret;
    ret=0;
    if(y == k){
        if(s[x] == 'X')return ret=0;
        ret=DP(x+1,y);
        if(ret)White[x] = 1;
        return ret;
    }
    if(x + c[y] - 1 >= n)return ret=0;
    bool OkWhite = 0, OkBlack = 0;
    if(s[x] == '_'){
        White[x] = 1;
        return ret=DP(x+1,y);
    }
    else if(s[x] == 'X'){
        add(x,x);
        if(GetSum(x,x+c[y]-1) == 0 && s[x+c[y]] != 'X')ret = DP(x+c[y]+1,y+1);
        if(ret){
            add(x,x+c[y]-1);
            White[x+c[y]] = 1;
        }
        return ret;
    }
    else{
        OkWhite = DP(x+1,y);
        if(GetSum(x,x+c[y]-1) == 0 && s[x+c[y]] != 'X'){
            OkBlack = DP(x+c[y]+1,y+1);
            if(OkBlack){
                add(x,x+c[y]-1);
                White[x+c[y]] = 1;
            }
        }
    }
    if(OkBlack && OkWhite) White[x] = 1, add(x,x);
    else if(OkBlack) add(x,x);
    else if(OkWhite) White[x] = 1;
    return ret=max(OkWhite, OkBlack);
}
string solve_puzzle(string S, vector<int> C){
    s=S;n=s.size();k=C.size();ans=s;s+="####";
    for(int i=0;i<n;i++)White[i] = 0;
    for(int i=0;i<k;i++)c[i]=C[i];
    for(int i=0;i<n;i++)if(ans[i] == '.')ans[i] = '?';

    Pref[0]=(s[0] == '_');
    for(int i=1;i<n;i++)Pref[i]=Pref[i-1] + (s[i] == '_');
    memset(dp,-1,sizeof(dp));
    DP(0,0);
    for(int i=0;i<n;i++){
        if(i)BL[i] += BL[i-1];
        if(BL[i] && White[i])ans[i] = '?';
        else if(BL[i]) ans[i] = 'X';
        else ans[i]='_';
    }
    return ans;
}

• 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