Submission #274967

#	Time	Username	Problem	Language	Result	Execution time	Memory
274967		hamerin	Paint By Numbers (IOI16_paint)	C++17	0 / 100	1 ms	384 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

vector<int> WpfS, BpfS;
int N, K;

// W를 [l, r]에 놓는 게 가능한가?
bool Wp(int l, int r) { return l == 0 || l > r || BpfS[r] == BpfS[l - 1]; }

// B를 [l, r]에 놓는 게 가능한가?
bool Bp(int l, int r) { return l == 0 || l > r || WpfS[r] == WpfS[l - 1]; }

vector<vector<bool>> fill_dynamic(string &s, vector<int> &c, bool rev = false) {
    if (rev) {
        reverse(iterall(s));
        reverse(iterall(c));
    }

    WpfS.resize(N + 1, 0);
    BpfS.resize(N + 1, 0);
    fill(iterall(WpfS), 0);
    fill(iterall(BpfS), 0);

    for (int i = 0; i < N; i++) {
        if (s[i] == '_') WpfS[i + 1] = 1;
        if (s[i] == 'X') BpfS[i + 1] = 1;
        WpfS[i + 1] += WpfS[i];
        BpfS[i + 1] += BpfS[i];
    }

    vector<vector<bool>> D(N + 1, vector<bool>(K + 1));
    vector<vector<bool>> F(N + 1, vector<bool>(K + 1));

    for (int i = 0; i <= N; i++) D[i][0] = true;
    // for (int i = 0; i <= K; i++) D[0][i] = true;

    for (int i = c[0]; i <= N; i++) {
        F[i][1] = Wp(1, i - c[0]);
        D[i][1] = F[i][1] && Bp(i - c[0] + 1, i);
    }

    for (int j = 2; j <= K; j++) {
        for (int i = c[j - 1] + 1; i <= N; i++) {
            F[i][j] = Wp(i - c[j - 1], i - c[j - 1]) &&
                      (F[i - 1][j] || D[i - c[j - 1] - 1][j - 1]);
            D[i][j] = Bp(i - c[j - 1] + 1, i) && F[i][j];
        }
    }

    if (rev) {
        reverse(iterall(s));
        reverse(iterall(c));
    }

    return D;
}


string solve_puzzle(string s, vector<int> c) {
    N = (int)s.size();
    K = (int)c.size();

    auto Dfor = fill_dynamic(s, c);
    auto Drev = fill_dynamic(s, c, true);
    vector<vector<bool>> D(N + 1, vector<bool>(K + 1));

    for (int j = 1; j <= K; j++) {
        for (int i = c[j - 1]; i <= N; i++)
            D[i][j] = (Dfor[i][j] && Drev[N - i + c[j - 1]][K - j + 1]);
    }

    vector<int> res(N);
    for (int i = 1; i <= N; i++)
        if (s[i - 1] == 'X') res[i] = 2;

    for (int j = 1; j <= K; j++) {
        vector<int> p(N + 1);
        for (int i = 1; i <= N; i++) p[i] = p[i - 1] + D[i][j];

        vector<int> tmp(N + 1);
        for (int i = 1; i <= N; i++) {
            int r = min(N, i + c[j - 1] - 1);
            int l = i - 1;
            int d = p[r] - p[l];

            if (d == p.back())
                tmp[i] = 2;
            else if (d != 0)
                tmp[i] = 1;
        }

        for (int i = 1; i <= N; i++) res[i] = max(res[i], tmp[i]);
    }


    string ret;
    vector<char> mp = {'_', '?', 'X'};
    for (int i = 1; i <= N; i++) ret.push_back(mp[res[i]]);
    assert(ret.size() == N);

    return ret;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from paint.cpp:3:
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:115:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |     assert(ret.size() == N);
      |            ~~~~~~~~~~~^~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10