Submission #370162

#	Time	Username	Problem	Language	Result	Execution time	Memory
370162		urd05	Paint By Numbers (IOI16_paint)	C++14	59 / 100	4 ms	492 KiB

paint

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

bool dp[200000][100];
bool dp1[200000][100];
bool black[200000];
bool white[200000];

string solve_puzzle(string s,vector<int> c) {
    int n=s.size();
    int k=c.size();
    for(int j=0;j<k;j++) {
        int cnt=0;
        for(int i=0;i<c[j];i++) {
            if (s[i]=='_') {
                cnt++;
            }
        }
        deque<int> dq;
        bool flag=false;
        for(int i=0;i<n;i++) {
            if (j==0) {
                dq.push_front(i);
            }
            if (j!=0&&i>c[j-1]&&dp[i-c[j-1]-1][j-1]) {
                dq.push_front(i-c[j-1]-1);
            }
            if (!dq.empty()&&cnt==0&&(j!=0||!flag)) {
                dp[i][j]=true;
            }
            if (s[i]=='X') {
                flag=true;
                while (dq.back()<=i-(j==0?0:c[j-1])) {
                    dq.pop_back();
                }
            }
            if (s[i]=='_') {
                cnt--;
            }
            if (i+c[j]<n&&s[i+c[j]]=='_') {
                cnt++;
            }
        }
    }
    for(int j=k-1;j>=0;j--) {
        int cnt=0;
        for(int i=n-c[j];i<n;i++) {
            if (s[i]=='_') {
                cnt++;
            }
        }
        deque<int> dq;
        bool flag=false;
        for(int i=n-1;i>=0;i--) {
            if (j==k-1) {
                dq.push_front(i);
            }
            if (j!=k-1&&i+c[j+1]+1<n&&dp1[i+c[j+1]+1][j+1]) {
                dq.push_front(i+c[j+1]+1);
            }
            if (!dq.empty()&&cnt==0&&(j!=k-1||!flag)) {
                dp1[i][j]=true;
            }
            if (s[i]=='X') {
                flag=true;
                while (dq.back()>=i+(j==k-1?0:c[j+1])) {
                    dq.pop_back();
                }
            }
            if (s[i]=='_') {
                cnt--;
            }
            if (i-c[j]>=0&&s[i-c[j]]=='_') {
                cnt++;
            }
        }
    }
    for(int j=0;j<k;j++) {
        int cnt=0;
        for(int i=0;i<n;i++) {
            //printf("%d %d\n",dp[i][0],dp1[i][0]);
            if (i-c[j]>=0&&dp[i-c[j]][j]&&dp1[i-1][j]) {
                //printf("- %d\n",i-c[j]);
                cnt--;
            }
            if (i+c[j]-1<n&&dp[i][j]&&dp1[i+c[j]-1][j]) {
                //printf("+ %d\n",i);
                cnt++;
            }
            if (cnt!=0) {
                black[i]=true;
            }
        }
    }
    string ret;
    for(int j=0;j<=k;j++) {
        int cnt=0;
        for(int i=1;i<n;i++) {
            if (j!=k&&i+c[j]-1<n&&dp[i][j]&&dp1[i+c[j]-1][j]) {
                cnt++;
            }
        }
        bool flag=false;
        if (j==0) {
            flag=true;
        }
        if (j==k) {
            cnt=1e9;
        }
        for(int i=0;i<n;i++) {
            if (i) {
                if (j!=0&&i>=c[j-1]&&dp[i-c[j-1]][j-1]&&dp1[i-1][j-1]) {
                    flag=true;
                }
            }
            if (cnt!=0&&flag) {
                white[i]=true;
            }
            if (i!=n-1) {
                if (j!=k&&i+1+c[j]-1<n&&dp[i+1][j]&&dp1[i+1+c[j]-1][j]) {
                    cnt--;
                }
            }
        }
    }
    for(int i=0;i<n;i++) {
        if (s[i]=='X') {
            white[i]=false;
        }
        if (s[i]=='_') {
            black[i]=false;
        }
        if (black[i]&&white[i]) {
            ret.push_back('?');
        }
        else if (black[i]) {
            ret.push_back('X');
        }
        else {
            ret.push_back('_');
        }
    }
    return ret;
}

• 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