제출 #774055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
774055		PoonYaPat	Paint By Numbers (IOI16_paint)	C++14	90 / 100	120 ms	211468 KiB

paint

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

struct node {
    int n,k,mode;
};

int n,m,bef[20010],mark[20010];
bool dp[20010][110][2],canX[20010],canY[20010];
string ans;
vector<node> adj[20010][110][2];
bool vis[20010][110][2];

string solve_puzzle(string s, vector<int> c) {
    n=s.size();
    m=c.size();
    int before=0;
    s=" "+s;

    for (int i=1; i<=n; ++i) {
        if (s[i]=='_') before=i;
        bef[i]=before;
    }

    dp[0][0][0]=true;
    for (int i=1; i<=n; ++i) {
        for (int j=0; j<=m; ++j) {
            if (s[i]!='X') {
                if (dp[i-1][j][0]) {
                    dp[i][j][0]=true;
                    adj[i][j][0].push_back({i-1,j,0});
                }

                if (j && dp[i-1][j-1][1]) {
                    dp[i][j][0]=true;
                    adj[i][j][0].push_back({i-1,j-1,1});
                }
            }
            if (s[i]!='_') {
                if (i-bef[i]>=c[j] && i>=c[j] && dp[i-c[j]][j][0] && j<m) {
                    dp[i][j][1]=true;
                    adj[i][j][1].push_back({i-c[j],j,0});
                }
            }
        }
    }

    queue<node> q;
    if (dp[n][m][0]) q.push({n,m,0});
    if (dp[n][m-1][1]) q.push({n,m-1,1});

    while (!q.empty()) {
        int a=q.front().n, b=q.front().k, mode=q.front().mode;
        q.pop();

        if (vis[a][b][mode]) continue;
        vis[a][b][mode]=true;

        if (mode==0) canY[a]=true;
        if (mode==1) ++mark[a-c[b]+1], --mark[a+1];

        for (auto s : adj[a][b][mode]) q.push(s);
    }

    for (int i=1; i<=n; ++i) {
        mark[i]+=mark[i-1];
        if (mark[i]) canX[i]=true;
    }

    for (int i=1; i<=n; ++i) {
        if (s[i]=='X') ans+='X';
        else if (s[i]=='Y') ans+='Y';
        else {
            if (canX[i] && canY[i]) ans+='?';
            else if (canX[i]) ans+='X';
            else if (canY[i]) ans+='_';
        }
    }
    return ans;
}

• 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