Submission #595080

#	Time	Username	Problem	Language	Result	Execution time	Memory
595080		Valaki2	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	340 KiB

paint

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

#define pb push_back

void calc_dp(int n, string s, int k, vector<int> c, vector<vector<int> > &cmin, vector<vector<int> > &cmax, vector<vector<bool> > &w) {
    cmin.assign(1 + n, vector<int> (1 + k, -1));
    cmax.assign(1 + n, vector<int> (1 + k, -1));
    w.assign(1 + n, vector<bool> (1 + k, false));
    w[0][0] = true;
    for(int i = 1; i <= n; i++) {
        if(s[i] == 'X' || s[i] == '.') {
            for(int j = 1; j <= k; j++) {
                cmin[i][j] = n + 1;
                if(w[i - 1][j - 1]) {
                    cmin[i][j] = 1;
                    cmax[i][j] = 1;
                }
                if(cmin[i - 1][j] != -1) {
                    cmin[i][j] = min(cmin[i][j], cmin[i - 1][j] + 1);
                    cmax[i][j] = max(cmax[i][j], cmax[i - 1][j] + 1);
                }
                cmax[i][j] = min(cmax[i][j], c[j]);
                if(cmin[i][j] > cmax[i][j]) {
                    cmin[i][j] = -1;
                    cmax[i][j] = -1;
                }
            }
        }
        if(s[i] == '_' || s[i] == '.') {
            for(int j = 0; j <= k; j++) {
                if(cmax[i - 1][j] == c[j]) {
                    w[i][j] = true;
                }
                if(w[i - 1][j]) {
                    w[i][j] = true;
                }
            }
        }
    }
}

vector<vector<int> > left_min;
vector<vector<int> > left_max;
vector<vector<bool> > left_w;
vector<vector<int> > right_min;
vector<vector<int> > right_max;
vector<vector<bool> > right_w;

string solve_puzzle(string s, vector<signed> c) {
    int n = (int) s.size();
    int k = (int) c.size();
    // calculate left dp
    string s1 = s;
    reverse(s1.begin(), s1.end());
    s1.pb('!');
    reverse(s1.begin(), s1.end());
    vector<int> c1;
    c1.pb(0);
    for(int i = 0; i < k; i++) {
        c1.pb(c[i]);
    }
    calc_dp(n, s1, k, c1, left_min, left_max, left_w);
    // calculate right dp
    string s2 = s;
    s2.pb('!');
    reverse(s2.begin(), s2.end());
    vector<int> c2;
    for(int i = 0; i < k; i++) {
        c2.pb(c[i]);
    }
    c2.pb(0);
    reverse(c2.begin(), c2.end());
    calc_dp(n, s2, k, c2, right_min, right_max, right_w);
    // calculate answer
    string ans(n, '!');
    for(int i = 1; i <= n; i++) {
        bool b = false;
        for(int idx = 1; idx <= k; idx++) {
            int j1 = idx, j2 = k + 1 - idx;
            int cur_left_min = left_min[i][j1];
            int cur_left_max = left_max[i][j1];
            int cur_right_max = right_min[n + 1 - i][j2];
            int cur_right_min = right_max[n + 1 - i][j2];
            if(cur_left_min == -1 || cur_right_min == -1 || cur_left_max == -1 || cur_right_max == -1) {
                continue;
            }
            cur_right_max = c1[j1] + 1 - cur_right_max;
            cur_right_min = c1[j1] + 1 - cur_right_min;
            if(max(cur_left_min, cur_right_min) <= min(cur_left_max, cur_right_max)) {
                b = true;
                break;
            }
        }
        bool w = false;
        for(int idx = 0; idx <= k; idx++) {
            int j1 = idx, j2 = k - idx;
            if(left_w[i][j1] && right_w[n + 1 - i][j2]) {
                w = true;
                break;
            }
        }
        char ch = '!';
        if(b && w) {
            ch = '?';
        }
        if(b && !w) {
            ch = 'X';
        }
        if(!b && w) {
            ch = '_';
        }
        ans[i - 1] = ch;
    }
    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