Submission #1342384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1342384		yogesh_sane	Paint By Numbers (IOI16_paint)	C++20	Compilation error	0 ms	0 KiB

paint

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

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

    // Make string 1-indexed
    s = " " + s;

    // Prefix sum: number of '_' up to i
    vector<int> underscore(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        underscore[i] = underscore[i - 1] + (s[i] == '_');
    }

    // Check if segment [l, r] has no '_'
    auto can_fill = [&](int l, int r) {
        return (underscore[r] - underscore[l - 1] == 0);
    };

    // dp1[i][j] = can we place first j blocks using prefix ending at i
    vector<vector<bool>> dp1(n + 1, vector<bool>(k + 1, false));
    for (int i = 0; i <= n; i++) dp1[i][0] = true;

    for (int j = 1; j <= k; j++) {
        int len = blocks[j - 1];
        for (int i = 1; i <= n; i++) {
            if (i < len) continue;

            if (!can_fill(i - len + 1, i)) continue;

            if (j == 1) {
                dp1[i][j] = true;
            } else {
                if (i - len - 1 >= 0 && dp1[i - len - 1][j - 1]) {
                    dp1[i][j] = true;
                }
            }
        }
    }

    // dp2[i][j] = can we place blocks j..k starting from i
    vector<vector<bool>> dp2(n + 2, vector<bool>(k + 2, false));
    for (int i = 1; i <= n + 1; i++) dp2[i][k + 1] = true;

    for (int j = k; j >= 1; j--) {
        int len = blocks[j - 1];
        for (int i = n; i >= 1; i--) {
            if (i + len - 1 > n) continue;

            if (!can_fill(i, i + len - 1)) continue;

            if (j == k) {
                dp2[i][j] = true;
            } else {
                if (i + len + 1 <= n && dp2[i + len + 1][j + 1]) {
                    dp2[i][j] = true;
                }
            }
        }
    }

    // Make dp prefix/suffix cumulative
    for (int j = 0; j <= k; j++) {
        for (int i = 1; i <= n; i++) {
            dp1[i][j] |= dp1[i - 1][j];
        }
    }

    for (int j = 1; j <= k + 1; j++) {
        for (int i = n; i >= 1; i--) {
            dp2[i][j] |= dp2[i + 1][j];
        }
    }

    // Difference array to track possible coverage
    vector<int> diff(n + 2, 0);

    // Positions that are always black
    vector<int> always_black(n + 1, 0);

    for (int j = 1; j <= k; j++) {
        int len = blocks[j - 1];

        int left = 1, right = n;

        for (int i = 1; i + len - 1 <= n; i++) {
            bool ok = true;

            // Check left side
            if (j > 1) {
                if (i - 2 < 0 || !dp1[i - 2][j - 1]) ok = false;
            }

            // Check right side
            if (j < k) {
                if (i + len + 1 > n || !dp2[i + len + 1][j + 1]) ok = false;
            }

            if (!ok) continue;
            if (!can_fill(i, i + len - 1)) continue;

            // Mark possible block placement
            diff[i] += 1;
            diff[i + len] -= 1;

            left = max(left, i);
            right = min(right, i + len - 1);
        }

        // Mark forced cells (intersection of all placements)
        if (left <= right) {
            for (int x = left; x <= right; x++) {
                always_black[x] = 1;
            }
        }
    }

    // Build final answer
    string ans = "";
    int coverage = 0;

    for (int i = 1; i <= n; i++) {
        coverage += diff[i];

        if (always_black[i]) ans += 'X';
        else if (coverage == 0) ans += '_';
        else ans += '?';
    }

    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:68:23: error: no match for 'operator|=' (operand types are 'std::vector<bool>::reference' and 'std::vector<bool>::reference')
   68 |             dp1[i][j] |= dp1[i - 1][j];
      |             ~~~~~~~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:176,
                 from paint.cpp:2:
/usr/include/c++/13/future:179:18: note: candidate: 'std::launch& std::operator|=(launch&, launch)'
  179 |   inline launch& operator|=(launch& __x, launch __y) noexcept
      |                  ^~~~~~~~
/usr/include/c++/13/future:179:37: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::launch&'
  179 |   inline launch& operator|=(launch& __x, launch __y) noexcept
      |                             ~~~~~~~~^~~
In file included from /usr/include/c++/13/format:39,
                 from /usr/include/c++/13/bits/chrono_io.h:39,
                 from /usr/include/c++/13/chrono:3370,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:172:
/usr/include/c++/13/charconv:657:3: note: candidate: 'constexpr std::chars_format& std::operator|=(chars_format&, chars_format)'
  657 |   operator|=(chars_format& __lhs, chars_format __rhs) noexcept
      |   ^~~~~~~~
/usr/include/c++/13/charconv:657:28: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::chars_format&'
  657 |   operator|=(chars_format& __lhs, chars_format __rhs) noexcept
      |              ~~~~~~~~~~~~~~^~~~~
In file included from /usr/include/c++/13/streambuf:43,
                 from /usr/include/c++/13/bits/streambuf_iterator.h:35,
                 from /usr/include/c++/13/iterator:66,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54:
/usr/include/c++/13/bits/ios_base.h:182:3: note: candidate: 'const std::_Ios_Iostate& std::operator|=(_Ios_Iostate&, _Ios_Iostate)'
  182 |   operator|=(_Ios_Iostate& __a, _Ios_Iostate __b)
      |   ^~~~~~~~
/usr/include/c++/13/bits/ios_base.h:182:28: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::_Ios_Iostate&'
  182 |   operator|=(_Ios_Iostate& __a, _Ios_Iostate __b)
      |              ~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/ios_base.h:142:3: note: candidate: 'const std::_Ios_Openmode& std::operator|=(_Ios_Openmode&, _Ios_Openmode)'
  142 |   operator|=(_Ios_Openmode& __a, _Ios_Openmode __b)
      |   ^~~~~~~~
/usr/include/c++/13/bits/ios_base.h:142:29: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::_Ios_Openmode&'
  142 |   operator|=(_Ios_Openmode& __a, _Ios_Openmode __b)
      |              ~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/ios_base.h:99:3: note: candidate: 'const std::_Ios_Fmtflags& std::operator|=(_Ios_Fmtflags&, _Ios_Fmtflags)'
   99 |   operator|=(_Ios_Fmtflags& __a, _Ios_Fmtflags __b)
      |   ^~~~~~~~
/usr/include/c++/13/bits/ios_base.h:99:29: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::_Ios_Fmtflags&'
   99 |   operator|=(_Ios_Fmtflags& __a, _Ios_Fmtflags __b)
      |              ~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/13/bits/memory_resource.h:38,
                 from /usr/include/c++/13/string:58,
                 from paint.h:3,
                 from paint.cpp:1:
/usr/include/c++/13/cstddef:167:3: note: candidate: 'constexpr std::byte& std::operator|=(byte&, byte)'
  167 |   operator|=(byte& __l, byte __r) noexcept
      |   ^~~~~~~~
/usr/include/c++/13/cstddef:167:20: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::byte&'
  167 |   operator|=(byte& __l, byte __r) noexcept
      |              ~~~~~~^~~
paint.cpp:74:23: error: no match for 'operator|=' (operand types are 'std::vector<bool>::reference' and 'std::vector<bool>::reference')
   74 |             dp2[i][j] |= dp2[i + 1][j];
      |             ~~~~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/c++/13/future:179:18: note: candidate: 'std::launch& std::operator|=(launch&, launch)'
  179 |   inline launch& operator|=(launch& __x, launch __y) noexcept
      |                  ^~~~~~~~
/usr/include/c++/13/future:179:37: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::launch&'
  179 |   inline launch& operator|=(launch& __x, launch __y) noexcept
      |                             ~~~~~~~~^~~
/usr/include/c++/13/charconv:657:3: note: candidate: 'constexpr std::chars_format& std::operator|=(chars_format&, chars_format)'
  657 |   operator|=(chars_format& __lhs, chars_format __rhs) noexcept
      |   ^~~~~~~~
/usr/include/c++/13/charconv:657:28: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::chars_format&'
  657 |   operator|=(chars_format& __lhs, chars_format __rhs) noexcept
      |              ~~~~~~~~~~~~~~^~~~~
/usr/include/c++/13/bits/ios_base.h:182:3: note: candidate: 'const std::_Ios_Iostate& std::operator|=(_Ios_Iostate&, _Ios_Iostate)'
  182 |   operator|=(_Ios_Iostate& __a, _Ios_Iostate __b)
      |   ^~~~~~~~
/usr/include/c++/13/bits/ios_base.h:182:28: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::_Ios_Iostate&'
  182 |   operator|=(_Ios_Iostate& __a, _Ios_Iostate __b)
      |              ~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/ios_base.h:142:3: note: candidate: 'const std::_Ios_Openmode& std::operator|=(_Ios_Openmode&, _Ios_Openmode)'
  142 |   operator|=(_Ios_Openmode& __a, _Ios_Openmode __b)
      |   ^~~~~~~~
/usr/include/c++/13/bits/ios_base.h:142:29: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::_Ios_Openmode&'
  142 |   operator|=(_Ios_Openmode& __a, _Ios_Openmode __b)
      |              ~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/ios_base.h:99:3: note: candidate: 'const std::_Ios_Fmtflags& std::operator|=(_Ios_Fmtflags&, _Ios_Fmtflags)'
   99 |   operator|=(_Ios_Fmtflags& __a, _Ios_Fmtflags __b)
      |   ^~~~~~~~
/usr/include/c++/13/bits/ios_base.h:99:29: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::_Ios_Fmtflags&'
   99 |   operator|=(_Ios_Fmtflags& __a, _Ios_Fmtflags __b)
      |              ~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/cstddef:167:3: note: candidate: 'constexpr std::byte& std::operator|=(byte&, byte)'
  167 |   operator|=(byte& __l, byte __r) noexcept
      |   ^~~~~~~~
/usr/include/c++/13/cstddef:167:20: note:   no known conversion for argument 1 from 'std::vector<bool>::reference' to 'std::byte&'
  167 |   operator|=(byte& __l, byte __r) noexcept
      |              ~~~~~~^~~