제출 #367494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
367494		BartolM	Paint By Numbers (IOI16_paint)	C++17	90 / 100	174 ms	84588 KiB

paint

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

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=2e5+2;
const int K=102;

int n, k;
int dp[N][K];
int pref[2][N];
int crn[N], bel[N];
string res;
#define DEBUG 0

string solve_puzzle(string s, vector<int> c) {
    n=s.size(); k=c.size();
    s=" "+s;
    pref[0][0]=pref[1][0]=0;
    for (int i=1; i<=n; ++i) {
        pref[0][i]=pref[0][i-1]+(s[i]=='_');
        pref[1][i]=pref[1][i-1]+(s[i]=='X');
    }

    memset(dp, 0, sizeof dp);
    memset(crn, 0, sizeof crn);
    memset(bel, 0, sizeof bel);
    dp[0][0]=1;

    for (int i=1; i<=n; ++i) {
        if (s[i]!='X') dp[i][0]=dp[i-1][0];
        for (int j=1; j<=k; ++j) {
            if (s[i]!='X') dp[i][j]|=dp[i-1][j];
            if (i>=c[j-1] && pref[0][i]-pref[0][i-c[j-1]]==0 && s[i-c[j-1]]!='X') dp[i][j]|=dp[i-c[j-1]-(j>1)][j-1];
        }
    }
    #if DEBUG
        for (int i=k; i>=0; --i) {
            for (int j=0; j<=n; ++j) {
                printf("%d ", dp[j][i]);
            }
            printf("\n");
        }
        printf("----------------\n");
    #endif // DEBUG
    assert(dp[n][k]);
    dp[n][k]++;
    for (int i=n; i>0; --i) {
        for (int j=0; j<=k; ++j) {
            if (dp[i][j]<2) continue;
            if (s[i]!='X' && dp[i-1][j]) {
                dp[i-1][j]++;
                bel[i]++;
            }
            if (j && i>=c[j-1] && pref[0][i]-pref[0][i-c[j-1]]==0 && s[i-c[j-1]]!='X' && dp[i-c[j-1]-(j>1)][j-1]) {
                crn[i-c[j-1]+1]++; crn[i+1]--; bel[i-c[j-1]]++;
//                printf("interval: [%d, %d]\n", i-c[j-1]+1, i);
                dp[i-c[j-1]-(j>1)][j-1]++;
            }
        }
    }


    #if DEBUG
        for (int i=k; i>=0; --i) {
            for (int j=0; j<=n; ++j) {
                printf("%d ", dp[j][i]>1 ? 1 : 0);
            }
            printf("\n");
        }
        printf("----------------\n");
    #endif // DEBUG

    for (int i=1; i<=n; ++i) crn[i]+=crn[i-1];
    for (int i=1; i<=n; ++i) {
        if (bel[i] && crn[i]) res+='?';
        else if (crn[i]) res+='X';
        else if (bel[i]) res+='_';
        else assert(0);
    }
    return res;
}

• 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: 0 / 10