제출 #138104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138104		Hassoony	Paint By Numbers (IOI16_paint)	C++17	59 / 100	80 ms	80376 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,Black[MX],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)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){
            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;
    for(int i=0;i<n;i++)Black[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: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10