제출 #1151419

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

paint

#include <bits/stdc++.h>
#include "paint.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 200'001;
const int K = 101;
int dp0[N][K], dp1[N][K];
int sum[N];
int cz1[N], cz0[N];

string solve_puzzle(string s, vector<int> c)
{
    int n = s.size(), k = c.size();
    s = '+' + s;
    for(int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + (int)(s[i] == '_');
    dp0[0][0] = 1;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 0; s[i] != 'X' && j <= k; ++j)
            dp0[i][j] |= (dp0[i - 1][j] | dp1[i - 1][j]);
        for(int j = 1; j <= k && s[i] != '_'; ++j)
            if(sum[i] - sum[i - c[j - 1]] == 0)
                dp1[i][j] |= dp0[i - c[j - 1]][j - 1];
    }
    if(dp0[n][k] == 1) dp0[n][k] = 2;
    if(dp1[n][k] == 1) dp1[n][k] = 2;
    for(int i = n; i >= 1; --i)
    {
        for(int j = 0; j <= k; ++j)
        {
            if(dp0[i][j] != 2) continue;
            cz0[i] = 1;
            if(dp0[i - 1][j] == 1)
                dp0[i - 1][j] = 2;
            if(dp1[i - 1][j] == 1)
                dp1[i - 1][j] = 2;
        }
        for(int j = 1; j <= k; ++j)
        {
            if(dp1[i][j] != 2) continue;
            cz1[i - c[j - 1] + 1] += 1; cz1[i + 1] -= 1;
            if(dp0[i - c[j - 1]][j - 1] == 1)
                dp0[i - c[j - 1]][j - 1] = 2;
        }
    }
    string ans;
    for(int i = 1; i <= n; ++i)
    {
        cz1[i] += cz1[i - 1];
        if(cz1[i] && cz0[i])
            ans.pb('?');
        else
        {
            if(cz1[i])
                ans.pb('X');
            else
                ans.pb('_');
        }
    }
    return ans;
}

컴파일 시 표준 에러 (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