Submission #889612

#	Time	Username	Problem	Language	Result	Execution time	Memory
889612		Ghulam_Junaid	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	600 KiB

paint

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

const int N = 2e5 + 10;
const int K = 105;

int pref[N], suff[N];
int need_pref[K], need_suff[K];


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

//     std::string ans = s;
//     int sz = c[0];
//     for (int i=0; i<n; i++)
//         ans[i] = '?';

//     int l = n - sz;
//     int r = sz - 1;
//     for (int i=l; i<=r; i++)
//         ans[i] = 'X';
//     return ans;
// }

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

    string ans = s;

    need_pref[0] = -2;
    for (int i=0; i<k; i++){
        int blacks = c[i];
        int available = 0;
        for (int j=need_pref[i] + 2; j<n; j++){
            available += (s[j] == '.');
            if (available == blacks){
                need_pref[i + 1] = j;
                break;
            }

            if (s[j] == '_')
                available = 0;
        }
    }

    for (int i=0; i<n; i++){
        for (int j=0; j<=k; j++){
            if (need_pref[j] > i)
                break;
            pref[i] = j;
        }
    }

    need_suff[k] = n + 1;
    for (int i=k - 1; i >= 0; i--){
        int blacks = c[i];
        int available = 0;
        for (int j=need_suff[i + 1] - 2; j >= 0; j--){
            available += (s[j] == '.');
            if (available == blacks){
                need_suff[i] = j;
                break;
            }

            if (s[j] == '_')
                available = 0;
        }
    }

    for (int i=n-1; i>=0; i--){
        for (int j=k; j>=0; j--){
            if (need_suff[j] < i)
                break;
            suff[i] = k - j;
        }
    }

    for (int i=0; i<n; i++){
        if (s[i] != '.') continue;

        // is this character always black or never black.

        // If I make it white, is the puzzle still solvable?
        bool can_be_white = 0;
        int put_in_pref = 0;
        for (int j=0; j<=k; j++){
            if (need_pref[j] >= i)
                break;
            put_in_pref = j;
        }
        can_be_white = (need_suff[put_in_pref] > i);

        if (!can_be_white){
            ans[i] = 'X';
            continue; 
        }

        bool can_be_black = 0;
        int l = i;
        int r = i;
        for (int j=i+1; j<n; j++){
            if (s[j] != '.')
                break;
            r++;
        }
        for (int j=i-1; j>=0; j--){
            if (s[j] != '.')
                break;
            l--;
        }

        for (int j=0; j<k; j++){
            for (int st = l; st <= i; st++){
                int en = st + c[j] - 1;
                if (en < i)
                    continue;
                if (en > r)
                    continue;

                if (need_pref[j] < (st - 1) && need_suff[j + 1] > (en + 1))
                    can_be_black = 1;
            }
        }

        if (can_be_black)
            ans[i] = '?';
        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