제출 #961902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
961902		ThegeekKnight16	Paint By Numbers (IOI16_paint)	C++17	100 / 100	149 ms	9368 KiB

paint

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


std::string solve_puzzle(std::string v, std::vector<int> c) {
    int N = v.size(); v.insert(v.begin(), '.');
    int K = c.size(); c.insert(c.begin(), 0);
    vector<bitset<102>> dpPref(N+1, 0), dpSuf(N+2, 0);
    vector<int> sBranco(N+2);
    for (int i = 1; i <= N; i++) sBranco[i] = sBranco[i-1] + (int)(v[i] == '_');

    dpPref[0][0] = dpSuf[N+1][K+1] = 1;
    for (int i = 1; i <= N; i++)
    {
        if (v[i] == 'X') {dpPref[i] = 0; continue;}
        dpPref[i] = dpPref[i-1]; //i-1 tbm eh branco
        for (int k = 1; k <= K; k++)
            dpPref[i][k] = (dpPref[i][k] || ((i > c[k]) && (sBranco[i-1] - sBranco[i-c[k]-1] == 0) && dpPref[i-c[k]-1][k-1])); // i-1 eh preto da comp k
    }
    for (int i = N; i >= 1; i--)
    {
        if (v[i] == 'X') {dpSuf[i] = 0; continue;}
        dpSuf[i] = dpSuf[i+1]; //i+1 tbm eh branco
        for (int k = 1; k <= K; k++)
            dpSuf[i][k] = (dpSuf[i][k] || ((i + c[k] <= N) && (sBranco[i + c[k]] - sBranco[i] == 0) && dpSuf[i+c[k]+1][k+1])); // i+1 eh preto da comp k
    }

    vector<int> poss(N+2); //qtd de poss de i ser preto
    for (int k = 1; k <= K; k++)
        for (int ini = 1, fim = c[k]; fim <= N; ini++, fim++)
        {
            if (sBranco[fim] - sBranco[ini-1] > 0) continue;
            if (dpPref[ini-1][k-1] == 0) continue;
            if (dpSuf[fim+1][k+1] == 0) continue;
            poss[ini]++; poss[fim+1]--;
        }

    for (int i = 1; i <= N; i++) poss[i] += poss[i-1];

    string resp;
    for (int i = 1; i <= N; i++)
    {
        if (v[i] != '.') {resp += v[i]; continue;}
        bool canBeWhite = 0;
        for (int k = 0; k <= K; k++) canBeWhite = (canBeWhite || (dpPref[i][k] && dpSuf[i][k+1]));
        bool canBeBlack = (poss[i] > 0);
        if (canBeWhite && canBeBlack) resp += "?";
        else if (canBeWhite) resp += "_";
        else resp += "X";
    }
    return resp;
}

• 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