Submission #1316908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316908		nikaa123	Paint By Numbers (IOI16_paint)	C++20	59 / 100	1 ms	332 KiB

paint

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

string solve_puzzle(string s, vector<int> c) {
    int n = s.size();
    int k = c.size();

    vector <int> pref(n+5,0);
    for (int i = 1; i < n; i++) {
        pref[1+i] = pref[i] + (s[i] == '_');
    }
    vector <vector<int>> dp1(n+5,vector<int>(k+5,0));
    for (int i = 0; i <= n+3; i++) {
        dp1[i][0] = 1;
    }
    auto isblack = [&](int l, int r) {
        if (r > n) return false;
        return (pref[r]-pref[l-1] == 0);
    };
    for (int j = 1; j <= k; j++) {
        for (int i = 1; i <= n; i++) {
            dp1[i][j] = dp1[i-1][j];
            
            if (i >= c[j-1]) {
                int start = i-c[j-1]+1;
                if (isblack(start,i)) {
                    if (start == 1 && j == 1) dp1[i][j] = 1;
                    else if (start > 1 && s[start-2] != 'X' && dp1[start-2][j-1]) dp1[i][j] = 1; 
                }
            }
            
        }
    }

    vector <vector<int>> dp2(n+5,vector<int>(k+5,0));
    for (int i = n+3; i >= 0; i--) {
        dp2[i][k+1] = 1;
    }
    for (int j = k; j >= 1; j--) {
        for (int i = n; i >= 1; i--) {
            dp2[i][j] = dp2[i+1][j];
            if (i + c[j-1] - 1 <= n) {
                int end = i+c[j-1]-1;
                if (isblack(i,end)) {
                    if (end == n && j == k) dp2[i][j] = 1;
                    else if (end < n && s[end] != 'X' && dp2[end+2][j+1]) dp2[i][j] = 1;
                }
            }
        }
    }
    vector <int> canw(n+5,0),canb(n+5,0);
    
    for (int i = 1; i <= n; i++) {
        if (s[i-1] == 'X') continue;
        for (int j = 0; j <= k; j++) {
            if (dp1[i-1][j] && dp2[i+1][j+1]) {
                canw[i] = 1;
                break;
            }
        }
    }
    vector <int> d(n+5,0);
    for (int j = 1; j <= k; j++) {
        for (int i = 1; i <= n - c[j-1] + 1; i++)  {
            int end = i + c[j-1] - 1;
            if (isblack(i,end)) {
                bool okl = (i == 1 && j == 1) || (i > 1 && s[i-2] != 'X' && dp1[i-2][j-1]);
                bool okr = (end == n && j == k) || (i < n && s[end] != 'X' && dp2[end+2][j+1]);
                if (okl && okr) {
                    d[i]++;
                    d[end+1]--;
                }
            }
        } 
    }
    int cur = 0;
    for (int i = 1; i <= n; i++) {
        cur += d[i];
        if (cur > 0) {
            canb[i] = 1;
        }
    }

    string ans = "";
    for (int i = 1; i <= n; i++) {
        if (canb[i] && canw[i]) {
            ans += "?";
        } else if (canb[i]) {
            ans += "X";
        } else {
            ans += "_";
        }
    }

    return ans;
}

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: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10