Submission #1046097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046097		jer033	Paint By Numbers (IOI16_paint)	C++17	100 / 100	399 ms	330996 KiB

paint

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

vector<vector<int>> 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<int>> potential_index(n, vector<int> (2*k+1, 0));
    if (s[0]!='X')
        potential_index[0][0] = 1;
    if ((whites[0] == whites[c[0]]) and (s[c[0]]!='X'))
        potential_index[0][1] = c[0];
    for (int curr = 1; curr<n; curr++)
    {
        for (int pos = 0; pos <= (2*k); pos++)
        {
            if ((pos%2)==0)
            {
                //we are checking for whites
                if (s[curr]!='X')
                {
                    if ((potential_index[curr-1][pos] == 1) or ( ((pos >= 1) and (curr >= c[(pos/2)-1])) and (potential_index[curr-c[(pos/2)-1]][pos-1] == c[(pos/2)-1])) )
                        potential_index[curr][pos] = 1;
                }
            }
            else
            {
                int q = potential_index[curr-1][pos];
                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]>0) and (s[curr+streak]!='X'))  )
                    potential_index[curr][pos] = streak;
                else
                    potential_index[curr][pos] = max(q-1, 0);
            }
        }
    }
    return potential_index;
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
    vector<vector<int>> 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<int>> 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]>0) and (b[n-1-i][2*k-j]>0))
                    can_be_white = 1;
            }
            else
            {
                if ((a[i][j]>0) and (b[n-1-i][2*k-j]>0))
                    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