Submission #739593

#	Time	Username	Problem	Language	Result	Execution time	Memory
739593		Abrar_Al_Samit	Paint By Numbers (IOI16_paint)	C++17	80 / 100	81 ms	360 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

const int nax = 101;
string s;
int n, m;
int dp[nax][nax];
int segs[nax];
int pre[nax];

void init() {
    for(int i=0; i<n; ++i) {
        pre[i] = (s[i]=='_');
        if(i) pre[i] += pre[i-1];
    }
}
bool ok(int i, int j) {
    if(j>=n) return false;

    if(i==0) return pre[j]==0;
    return (pre[j] - pre[i-1]) == 0;
}
int solve(int i, int j) {
    if(i>=n) return j==m;

    int &ret = dp[i][j];
    if(ret!=-1) return ret;

    ret = 0;

    if(s[i]=='.') {
        if(j<m && ok(i, i+segs[j]-1)) { //black
            if(i+segs[j]<n && s[i+segs[j]]=='X');
            else ret |= solve(i+segs[j]+1, j+1);
        }

        ret |= solve(i+1, j); // white
    } else {
        if(s[i]=='X') {
            if(j<m && ok(i, i+segs[j]-1)) { //black
                if(i+segs[j]<n && s[i+segs[j]]=='X');
                else ret |= solve(i+segs[j]+1, j+1);
            }
        } else {
            ret |= solve(i+1, j); // white
        }
    }
    return ret;
}
string solve_puzzle(string t, vector<int> c) {
    n = t.size(), m = c.size();
    s = t;
    for(int i=0; i<m; ++i) {
        segs[i] = c[i];
    }

    string ret;
    for(int i=0; i<n; ++i) {
        memset(dp, -1, sizeof dp);
        if(s[i]=='X' || s[i]=='_') {
            ret.push_back(s[i]);
        } else {
            s[i] = 'X';
            init();

            int cnt = solve(0, 0);


            memset(dp, -1, sizeof dp);
            s[i] = '_';
            init();
            cnt += solve(0, 0) * 2;

            assert(cnt!=0);

            if(cnt==3) {
                ret.push_back('?');
            } else {
                if(cnt==1) ret.push_back('X');
                else ret.push_back('_');
            }
            s[i] = '.';
        }
    }
    return ret;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10