Submission #598973

#	Time	Username	Problem	Language	Result	Execution time	Memory
598973		snasibov05	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1859 ms	346964 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <bits/stdc++.h>

using namespace std;

const int mxn = 2e5 + 5, mxk = 1e2 + 5;
bool pref[mxn][mxk][2];
bool suf[mxn][mxk][2];

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

    vector<int> prefw(n+1);
    for (int i = 1; i <= n; ++i){
        prefw[i] = prefw[i-1] + (s[i] == '_');
    }

    pref[0][0][0] = true;
    for (int i = 1; i <= n; ++i){
        for (int j = 0; j <= k; ++j) {
            if (s[i] == '.' || s[i] == '_') pref[i][j][0] = pref[i-1][j][0] || pref[i-1][j][1];
            if (s[i] == 'X' || s[i] == '.') {
                if (j == 0) continue;
                if (i - c[j-1] < 0 || prefw[i] - prefw[i - c[j-1]] > 0 || !pref[i - c[j-1]][j-1][0]) continue;
                pref[i][j][1] = true;
            }
        }
    }

    suf[n+1][k+1][0] = true;
    for (int i = n; i >= 1; --i){
        for (int j = k+1; j >= 1; --j) {
            if (s[i] == '.' || s[i] == '_') suf[i][j][0] = suf[i+1][j][0] || suf[i+1][j][1];
            if (s[i] == 'X' || s[i] == '.') {
                if (j == k+1) continue;
                if (i + c[j-1] > n+1 || prefw[i + c[j-1] - 1] - prefw[i-1] > 0 || !suf[i + c[j-1]][j+1][0]) continue;
                suf[i][j][1] = true;
            }
        }
    }

    vector<bool> posb(n+1), posw(n+1);
    for (int i = 1; i <= n; ++i){
        if (s[i] == 'X') continue;
        for (int j = 0; j <= k; ++j) {
            posw[i] = posw[i] || ((pref[i-1][j][1] || pref[i-1][j][0]) && (suf[i+1][j+1][1] || suf[i+1][j+1][0]));
        }
    }

    vector<pair<int, int>> v;
    for (int j = 1; j <= k; ++j){
        for (int i = 1; i <= n; ++i) {
            if (!pref[i-1][j-1][0] || i + c[j-1] > n+1 || !suf[i + c[j-1]][j+1][0] || prefw[i + c[j-1] - 1] - prefw[i-1] > 0) continue;
            v.push_back(make_pair(i, i + c[j-1] - 1));
        }
    }

    sort(v.begin(), v.end());
    int sz = v.size();
    vector<pair<int, int>> arr;
    for (int i = 0; i < sz; ++i){
        int l = v[i].first;
        int r = v[i].second;
        while (i + 1 < sz && v[i+1].first <= r) r = max(r, v[++i].second);
        arr.push_back({l, r});
    }

    for (auto [l, r] : arr){
        for (int i = l; i <= r; ++i) posb[i] = true;
    }

    string res;
    for (int i = 1; i <= n; ++i){
        if (posw[i] && posb[i]) res.push_back('?');
        else if (posw[i]) res.push_back('_');
        else res.push_back('X');
    }

    return res;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:72:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     for (auto [l, r] : arr){
      |               ^

• 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