제출 #772811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
772811		Sharky	Paint By Numbers (IOI16_paint)	C++17	0 / 100	1 ms	340 KiB

paint

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

const int maxn = 2e5 + 1;
const int maxk = 101;

int n, k, c[maxk], d[maxn];
// string s;
bool L[maxn][maxk], R[maxn][maxk], possible[maxn][2];
int lst[maxn][maxk], nxt[maxn][maxk], lstw[maxn], nxtw[maxn], lstb[maxn], nxtb[maxn];

struct node {
    int i, j, l, r;
    node(int i, int j, int l, int r): i(i), j(j), l(l), r(r) {}
};

vector<node> b;
vector<pair<int, int>> st;

bool ok(int id) {
    return (id >= 1 && id <= n);
}

string solve_puzzle(string s, vector<int> C) {
    n = s.length();
    s = "a" + s;
    s += 'a';
    lstw[0] = lstb[0] = 0;
    nxtb[n + 1] = nxtw[n + 1] = n + 1;
    for (int i = 1; i <= n; i++) {
        lstw[i] = lstw[i - 1];
        lstb[i] = lstb[i - 1];
        if (s[i] == '_') lstw[i] = i;
        else if (s[i] == 'X') lstb[i] = i;
    }
    for (int i = n; i >= 1; i--) {
        nxtb[i] = nxtb[i + 1];
        nxtw[i] = nxtw[i + 1];
        if (s[i] == '_') nxtw[i] = i;
        else if (s[i] == 'X') nxtb[i] = i;
    }
    for (int i = 0; i <= n + 1; i++) for (int j = 0; j <= k; j++) lst[i][j] = nxt[i][j] = -1;
    for (int i = 1; i <= k; i++) c[i] = C[i - 1];
    for (int i = 0; i <= n; i++) {
        if (s[i] == 'X') break;
        lst[i][0] = i, L[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            lst[i][j] = lst[i - 1][j];
            if (s[i] == '_') continue;
            int idx = i - c[j];
            if (idx < 0 || idx > n || s[idx] == 'X' || s[i+1] == 'X') continue;
            int next_white = nxtw[idx + 1];
            if (next_white <= i) continue;
            if (idx == 0 && j > 1) continue;
            if ((idx == 0 && j == 1) || lst[idx - 1][j - 1] != -1) {
                if (!(idx == 0 && j == 1)) {
                    int pos = lst[idx - 1][j - 1];
                    int next_black = nxtb[pos + 1];
                    if (next_black <= idx) continue;
                    // cout << "debug: " << idx << ' ' << j << ' ' << lst[idx - 1][j - 1] << '\n';
                }
                L[i][j] = 1;
                lst[i][j] = i;
                b.emplace_back(i, j, idx + 1, i);
            }
            // cout << i << ' ' << j << ' ' << L[i][j] << '\n';
        }
    }
    for (int i = n + 1; i >= 1; i--) {
        if (s[i] == 'X') break;
        nxt[i][0] = i, R[i][0] = 1;
    }
    reverse(c + 1, c + k + 1);
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= k; j++) {
            nxt[i][j] = nxt[i + 1][j];
            if (s[i] == '_') continue;
            int idx = i + c[j];
            if (idx <= 0 || idx > n + 1 || s[idx] == 'X' || s[i-1] == 'X') continue;
            int last_white = lstw[idx - 1];
            if (last_white >= i) continue;
            if (idx == n + 1 && j > 1) continue;
            if ((idx == n + 1 && j == 1) || nxt[idx + 1][j - 1] != -1) {
                if (!(idx == n + 1 && j == 1)) {
                    int pos = nxt[idx + 1][j - 1];
                    int next_black = lstb[pos - 1];
                    if (next_black >= idx) continue;
                    // cout << "debug: " << idx << ' ' << j << ' ' << lst[idx - 1][j - 1] << '\n';
                }
                R[i][j] = 1;
                nxt[i][j] = i;
            }
            // cout << i << ' ' << j << ' ' << R[i][j] << '\n';
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            if (lst[i - 1][j] != -1 && nxt[i + 1][k - j] != -1 && s[i] != 'X') possible[i][0] = 1; 
        }
    }
    for (auto& [i, j, l, r] : b) {
        if (i == n && j != k) continue;
        if (i == n || (L[i][j] && s[i + 1] != 'X' && nxt[i + 2][k - j] != -1)) {
            d[l]++, d[r + 1]--;
            // cout << l << ' ' << r << '\n';
        }
    }
    for (int i = 1; i <= n; i++) {
        d[i] += d[i - 1];
        possible[i][1] = !!(d[i] > 0);
    }
    string ans;
    for (int i = 1; i <= n; i++) {
        if (possible[i][0] && possible[i][1]) ans += '?';
        else if (possible[i][0]) ans += '_';
        else if (possible[i][1]) ans += 'X';
        // else assert(false);
    }
    return ans;
}

• 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