Submission #1238542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238542		thuhienne	Paint By Numbers (IOI16_paint)	C++20	100 / 100	475 ms	46844 KiB

paint

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

int n,k;

bool dppref[200009][109],dpsuff[200009][109];
//dppref i j: tu vi tri 1 -> i,lieu co the tao ra duoc j block den dau tien khong?

bool mustwhite[200009],mustblack[200009];

int prewhite[200009],preblack[200009];
int tdgc[200009];

bool existwhite(int l,int r) {
    return (prewhite[r] - prewhite[l - 1]) != 0;
}

bool canbeblack(int l,int r) {
    return (l > 0) && (r <= n) && !existwhite(l,r);
}

string solve_puzzle(string fixed,vector <int> c) {
    //preprocessing
    n = fixed.size(),k = c.size();
    vector <int> clue(k + 1);
    for (int i = 1;i <= k;i++) clue[i] = c[i - 1];
    fixed = "!" + fixed;
    for (int i = 1;i <= n;i++) {
        prewhite[i] = prewhite[i - 1];
        preblack[i] = preblack[i - 1];
        if (fixed[i] == 'X') preblack[i]++;
        if (fixed[i] == '_') prewhite[i]++;
    }
    //dp calculating
    //dp prefix
    dppref[0][0] = 1;
    for (int i = 1;i <= n;i++) {
        for (int j = 0;j <= k;j++) {
            int siz = clue[j];
            if (fixed[i] != 'X') {
                dppref[i][j] |= dppref[i - 1][j];
            }
            if (fixed[i] != '_' && j != 0 && i >= siz) {
                int siz = clue[j];
                if (i == siz) {
                    if (j == 1) dppref[i][j] |= canbeblack(1,i);
                } else {
                    dppref[i][j] |= canbeblack(i - siz + 1,i) && (fixed[i - siz] != 'X') && dppref[i - siz - 1][j - 1];
                }
            }
        }
    }
    //dp suffix
    dpsuff[n + 1][0] = 1;
    for (int i = n;i >= 1;i--) {
        for (int j = k + 1;j >= 1;j--) {
            int siz = clue[j],d = k - j + 1;
            if (fixed[i] != 'X') {
                dpsuff[i][d] |= dpsuff[i + 1][d];
            }
            if (fixed[i] != '_' && d != 0 && n - i + 1 >= siz) {
                if (n - i + 1 == siz) {
                    if (d == 1) dpsuff[i][d] |= canbeblack(i,n);
                } else {
                    dpsuff[i][d] |= canbeblack(i,i + siz - 1) && (fixed[i + siz] != 'X') && dpsuff[i + siz + 1][d - 1];
                }
            }
        }
    }
    //check black
    for (int i = 1;i <= n;i++) {
        mustblack[i] = 1;
        for (int j = 0;j <= k;j++) {
            if (dppref[i - 1][j] && dpsuff[i + 1][k - j]) {
                mustblack[i] = 0;
                break;
            }
        }
    }
    //check white
    for (int group = 1;group <= k;group++) {
        int len = clue[group];
        for (int place = 1;place + len - 1 <= n;place++) {
            if (!canbeblack(place,place + len - 1)) continue;
            if ( !dppref[max(0,place - 2)][group - 1] || fixed[place - 1] == 'X' ) continue;
            if ( !dpsuff[min(n + 1,place + len + 1)][k - group] || fixed[place + len] == 'X' ) continue;
            tdgc[place]++;
            tdgc[place + len]--;
        }
    }
    for (int i = 1;i <= n;i++) {
        tdgc[i] += tdgc[i - 1];
        if (tdgc[i] >= 1) mustwhite[i] = 0;
        else mustwhite[i] = 1;
    }
    string ret;
    for (int i = 1;i <= n;i++) {
        if (fixed[i] != '.') ret.push_back(fixed[i]);
        else if (mustblack[i]) ret.push_back('X');
        else if (mustwhite[i]) ret.push_back('_');
        else ret.push_back('?');
    }
    return ret;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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