Submission #1046145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046145		jer033	Paint By Numbers (IOI16_paint)	C++17	100 / 100	331 ms	36888 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
using pii = pair<int, int>;

vector<vector<bool>> dp(std::string s, std::vector<int> c)
{
    int n = s.size();
    s = s+'_';
    int k = c.size();
    vector<int> whites(n+1, 0);
    for (int i=1; i<=n; i++)
    {
        if (s[i-1]=='_')
            whites[i] = whites[i-1]+1;
        else
            whites[i] = whites[i-1];
    }
    vector<vector<bool>> potential_index(n, vector<bool> (2*k+1, 0));
    vector<int> painted(2*k+1, -1);
    if (s[0]!='X')
        potential_index[0][0] = 1;
    if ((whites[0] == whites[c[0]]) and (s[c[0]]!='X'))
    {
        for (int i=0; i<c[0]; i++)
            potential_index[i][1] = 1;
        if (c[0]<n)
            potential_index[c[0]][2] = 1;
    }
    //cout << "nakarating dito\n";
    for (int curr = 1; curr<n; curr++)
    {
        //cout << "current index " << curr << '\n';
        for (int pos = 0; pos <= (2*k); pos++)
        {
            //cout << "pos " << pos << '\n';
            if ((pos%2)==0)
            {
                if (s[curr]!='X')
                {
                    if (potential_index[curr-1][pos] == 1)
                        potential_index[curr][pos] = 1;
                }
            }
            else
            {
                int streak_no = pos/2;
                int streak = c[streak_no];
                if (  (((curr+streak)<=n) and (whites[curr]==whites[curr+streak])) and ((potential_index[curr-1][pos-1]==1) and (s[curr+streak]!='X'))  )
                {
                    //cout << "checked in\n";
                    if ((curr+streak)<n)
                        potential_index[curr+streak][pos+1] = 1;
                    for (int i = max(painted[pos]+1, curr); i<(curr+streak); i++)
                        potential_index[i][pos] = 1;
                    painted[pos] = curr+streak-1;
                }
            }
        }
    }
    return potential_index;
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
    vector<vector<bool>> a = dp(s, c);

    int n = s.size();
    int k = c.size();

    /*for (int i=0; i<n; i++)
    {
        for (int j=0; j<=(2*k); j++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }*/

    string ss;
    for (int i=n-1; i>=0; i--)
        ss.push_back(s[i]);
    vector<int> cc;
    for (int i = k-1; i>=0; i--)
        cc.push_back(c[i]);
    vector<vector<bool>> b = dp(ss, cc);

    string ans;
    for (int i=0; i<n; i++)
    {
        bool can_be_white = 0;
        bool can_be_black = 0;
        for (int j=0; j<=(2*k); j++)
        {
            if ((j%2) == 0)
            {
                if ((a[i][j]) and (b[n-1-i][2*k-j]))
                    can_be_white = 1;
            }
            else
            {
                if ((a[i][j]) and (b[n-1-i][2*k-j]))
                    can_be_black = 1;
            }
        }
        if (can_be_white and can_be_black)
            ans.push_back('?');
        else if (can_be_white)
            ans.push_back('_');
        else if (can_be_black)
            ans.push_back('X');
        else
            ans.push_back('o');
    }
    return ans;
}

• 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