Submission #773549

#	Time	Username	Problem	Language	Result	Execution time	Memory
773549		neonaht	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	340 KiB

paint

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

const int S_MAX_LEN = 200 * 1000 + 5;

int qs_[S_MAX_LEN], qsX[S_MAX_LEN], most_left[S_MAX_LEN], most_right[S_MAX_LEN], dpL[S_MAX_LEN][102], dpR[S_MAX_LEN][102];

std::string solve_puzzle(std::string s, std::vector<int> c) {
    int sz = s.size(), k = c.size(), now = 0;
    string res = "";
    s = "_" + s + "_";

    for(int i=1; i<=sz+1; i++) {
        qs_[i] += qs_[i-1] + (s[i] == '_');
        qsX[i] += qsX[i-1] + (s[i] == 'X');
    }

    for(int i=1; i<=sz; i++) {
        if(s[i] == 'X' && now == 0) now = i;
        else if(s[i] != 'X') now = 0;
        most_left[i] = now;
    }

    now = 0;

    for(int i=sz; i>=1; i--) {
        if(s[i] == 'X' && now == 0) now = i;
        else if(s[i] != 'X') now = 0;
        most_right[i] = now;
    }

    for(int j=0; j<k; j++) {
        int x = c[j];
        for(int i=x; i<=sz; i++) {
            if(s[i] == 'X') {
                if(qs_[i] - qs_[i-x] == 0) dpL[i][j] = (j-1 < 0 ? 1 : dpL[i-x-1][j-1]);
                else dpL[i][j] = 0;
            }
            else if(qs_[i] - qs_[i-x] == 0 && s[i-x] != 'X') {
                if(j == 0) dpL[i][j] = 1;
                else dpL[i][j] = max(dpL[i-1][j], dpL[i-x-1][j-1]);
            }
            else dpL[i][j] = dpL[i-1][j];
        }
    }

    for(int j=k-1; j>-1; j--) {
        int x = c[j];
        for(int i=sz-x+1; i>=1; i--) {
            if(s[i] == 'X') {
                if(qs_[i+x-1] - qs_[i-1] == 0) dpR[i][j] = (j+1 == k ? 1 : dpR[i+x+1][j+1]);
                else dpR[i][j] = 0;
            }
            else if(qs_[i+x-1] - qs_[i-1] == 0 && s[i+x] != 'X') {
                if(j == k-1) dpR[i][j] = 1;
                else dpR[i][j] = max(dpR[i+1][j], dpR[i+x+1][j+1]);
            }
            else dpR[i][j] = dpR[i+1][j];
        }
    }

    for(int i=1; i<=sz; i++) {
        if(s[i] != '.') {
            res += s[i];
            continue;
        }

        bool canX = 0, can_ = 0;

        // _
        if((qsX[i] == 0 && dpR[i+1][0]) || (qsX[sz] - qsX[i-1] == 0 && dpL[i-1][k-1])) can_ = true;
        for(int j=0; j<k-1; j++) if(dpL[i-1][j] + dpR[i+1][j+1] == 2) can_ = true;

        // X
        int l = (most_left[i-1] == 0 ? i : most_left[i-1]);
        int r = (most_right[i+1] == 0 ? i : most_right[i+1]);
         for(int j=0; j<k; j++) {
            if(c[j] >= r - l + 1) {
                for(int a=r; a<=min(sz, l+c[j]-1); a++) {
                    if(qs_[a] - qs_[a-c[j]] > 0) continue;

                    if(s[a-c[j]] !='X' && s[a+1]!='X') {
                        if((j-1<0 ? (qsX[a-c[j]]>0 ? 0 : 1) : (a-c[j]-1<1 ? 0 : dpL[a-c[j]-1][j-1])) && (j+1>=k ? (qsX[sz]-qsX[a]>0 ? 0 : 1) : (a+2>sz ? 0 : dpR[a+2][j+1]))) canX = true;
                    }
                }
            }
         }

        if(can_ && canX) res += '?';
        else if(can_) res += '_';
        else res += 'X';
    }

    return res;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10