Submission #275755

#	Time	Username	Problem	Language	Result	Execution time	Memory
275755		hamerin	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1772 ms	101300 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]; }

pair<vector<vector<bool>>, 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));

    D[0][0] = true;
    for (int i = 1; i <= N; i++) D[i][0] = Wp(1, i);
    // 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];
        }
    }

    auto Da = D;
    for (int j = 1; j <= K; j++) {
        for (int i = 1; i <= N; i++) {
            Da[i][j] = D[i][j] || (Da[i - 1][j] && Wp(i, i));
        }
    }

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

    return {D, Da};
}


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

    auto [Dfor, Dfa] = fill_dynamic(s, c);
    auto [Drev, Dra] = 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 = 0; i < c[j - 1]; i++) cout << 0 << " ";
        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 + 1);

    for (int i = 1; i <= N; i++) {
        bool flag = false;
        for (int j = 0; j <= K; j++) {
            flag = flag || (Dfa[i - 1][j] && Dra[N - i][K - j]);
        }
        if (!flag) res[i] = 2;
    }

    vector<vector<pi>> bex(N + 1, vector<pi>());
    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> fl(N + 2, N + 1), fr(N + 2, N + 1);
        for (int i = N; i >= 1; i--) {
            if (D[i][j])
                fr[i] = i;
            else
                fr[i] = fr[i + 1];
        }
        for (int i = 1; i <= N; i++) {
            if (D[i][j])
                fl[i] = i;
            else
                fl[i] = fl[i - 1];
        }

        for (int i = 1; i <= N; i++) {
            if (s[i - 1] == 'X') {
                int lb = fr[i];
                int rb = fl[min(N, i + c[j - 1] - 1)];

                // cout << lb << " " << rb << endl;

                if (lb == N + 1 || rb == N + 1) continue;
                bex[i].emplace_back(rb - c[j - 1] + 1, lb);
            }
        }

        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]);
    }

    vector<pi> bmark;
    for (int i = 1; i <= N; i++) {
        if (s[i - 1] != 'X') continue;
        int s = 0, e = N + 1;
        for (auto [l, r] : bex[i]) s = max(s, l), e = min(e, r);
        if (s <= e) bmark.emplace_back(s, e);
    }

    sort(iterall(bmark));
    vector<pi> hap;
    for (auto [s, e] : bmark) {
        if (!hap.empty() && hap.back().second >= s)
            hap.back().second = max(hap.back().second, e);
        else
            hap.emplace_back(s, e);
    }

    for (auto [s, e] : hap) {
        for (int i = s; i <= e; i++) res[i] = 2;
    }

    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:179:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  179 |     assert(ret.size() == N);
      |            ~~~~~~~~~~~^~~~

• 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