Submission #417824

#	Time	Username	Problem	Language	Result	Execution time	Memory
417824		yuto1115	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1059 ms	246168 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;

bool dpl[200010][110][2];
bool dpr[200010][110][2];

string solve_puzzle(string s, vi c) {
    int n = s.size();
    int K = c.size();
    rep(_, 2) {
        vi wh(n + 1);
        rep(i, n) wh[i + 1] = wh[i] + (s[i] == '_');
        dpl[0][0][1] = true;
        rep(i, n) rep(j, K + 1) rep(k, 2) {
                    if (!dpl[i][j][k]) continue;
                    if (s[i] != 'X') dpl[i + 1][j][1] = true;
                    if (k and j < K and i + c[j] <= n and wh[i + c[j]] == wh[i]) {
                        dpl[i + c[j]][j + 1][0] = true;
                    }
                }
        reverse(all(s));
        reverse(all(c));
        swap(dpl, dpr);
    }
//    rep(i, n + 1) rep(j, K + 1) rep(k, 2) {
//                cout << i << ' ' << j << ' ' << k << ' ' << dpl[i][j][k] << endl;
//                cout << i << ' ' << j << ' ' << k << ' ' << dpr[i][j][k] << endl;
//            }
    vvi sum(K, vi(2 * n));
    rep(i, K) rep(j, 2 * n - 1) {
            int now = 0;
            if (j < n) {
                now = dpl[j + 1][i + 1][0] and dpr[n - j - 1][K - i - 1][1];
            }
            sum[i][j + 1] = sum[i][j] + now;
        }
    string ans = s;
    rep(i, n) {
        if (s[i] != '.') continue;
        bool b = false, w = false;
        rep(j, K + 1) {
            if (!dpl[i][j][0] and !dpl[i][j][1]) continue;
            if (!dpr[n - 1 - i][K - j][0] and !dpr[n - 1 - i][K - j][1]) continue;
//            cout << i << ' ' << j << endl;
            w = true;
        }
        rep(j, K) {
            if (sum[j][i + c[j]] - sum[j][i]) b = true;
        }
        assert(b or w);
        if (b and w) ans[i] = '?';
        else if (b) ans[i] = 'X';
        else ans[i] = '_';
    }
    return ans;
}

• 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