제출 #1324363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324363		sh_qaxxorov_571	Paint By Numbers (IOI16_paint)	C++20	100 / 100	317 ms	45648 KiB

paint

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

const int MAXN = 200005;
const int MAXK = 105;

bool pref[MAXN][MAXK], suff[MAXN][MAXK];
int can_x[MAXN], can_white[MAXN];
int sum_white[MAXN], sum_black[MAXN];

// Berilgan oraliqda oq katak bormi?
bool has_white(int l, int r) {
    if (l > r) return false;
    return (sum_white[r] - sum_white[l - 1]) > 0;
}

// Berilgan oraliqda qora katak bormi?
bool has_black(int l, int r) {
    if (l > r) return false;
    return (sum_black[r] - sum_black[l - 1]) > 0;
}

string solve_puzzle(string s, vector<int> c) {
    int n = s.length();
    int k = c.size();
    s = " " + s + " "; // 1-indexed qilish uchun

    for (int i = 1; i <= n; i++) {
        sum_white[i] = sum_white[i - 1] + (s[i] == '_');
        sum_black[i] = sum_black[i - 1] + (s[i] == 'X');
    }

    // Oldindan hisoblash (Prefix DP)
    pref[0][0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            // Holat 1: i-katak oq bo'lishi mumkinmi?
            if (s[i] != 'X' && pref[i - 1][j]) {
                pref[i][j] = true;
            }
            // Holat 2: i-katak j-blokning oxiri bo'lishi mumkinmi?
            if (j > 0 && i >= c[j - 1]) {
                int start = i - c[j - 1] + 1;
                if (!has_white(start, i)) { // Blok ichida oq katak yo'q
                    if (start == 1) {
                        if (j == 1) pref[i][j] = true;
                    } else if (s[start - 1] != 'X' && pref[start - 2][j - 1]) {
                        pref[i][j] = true;
                    }
                }
            }
        }
    }

    // Orqadan hisoblash (Suffix DP)
    suff[n + 1][k + 1] = true;
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= k + 1; j++) {
            if (s[i] != 'X' && suff[i + 1][j]) {
                suff[i][j] = true;
            }
            if (j <= k && i + c[j - 1] - 1 <= n) {
                int end = i + c[j - 1] - 1;
                if (!has_white(i, end)) {
                    if (end == n) {
                        if (j == k) suff[i][j] = true;
                    } else if (s[end + 1] != 'X' && suff[end + 2][j + 1]) {
                        suff[i][j] = true;
                    }
                }
            }
        }
    }

    // Kataklarni tekshirish
    for (int i = 1; i <= n; i++) {
        // Oq bo'lishi mumkinmi?
        for (int j = 0; j <= k; j++) {
            if (s[i] != 'X' && pref[i - 1][j] && suff[i + 1][j + 1]) {
                can_white[i] = 1;
                break;
            }
        }
        // Qora bo'lishi mumkinmi?
    }

    // Bloklarni tekshirish (qaysi kataklar qora blokning qismi bo'la oladi)
    for (int j = 1; j <= k; j++) {
        int len = c[j - 1];
        for (int i = 1; i <= n - len + 1; i++) {
            int end = i + len - 1;
            bool possible = false;
            if (!has_white(i, end)) {
                bool p_ok = (i == 1 && j == 1) || (i > 1 && s[i - 1] != 'X' && pref[i - 2][j - 1]);
                bool s_ok = (end == n && j == k) || (end < n && s[end + 1] != 'X' && suff[end + 2][j + 1]);
                if (p_ok && s_ok) possible = true;
            }
            if (possible) {
                can_x[i]++;
                can_x[end + 1]--;
            }
        }
    }

    int cur_x = 0;
    string res = "";
    for (int i = 1; i <= n; i++) {
        cur_x += can_x[i];
        if (cur_x > 0 && can_white[i]) res += '?';
        else if (cur_x > 0) res += 'X';
        else res += '_';
    }
    return res;
}

컴파일 시 표준 에러 (stderr) 메시지

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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