Submission #824803

#	Time	Username	Problem	Language	Result	Execution time	Memory
824803		vnm06	Paint By Numbers (IOI16_paint)	C++14	100 / 100	487 ms	44116 KiB

paint

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

int n, k;
int brw[200005];
bool pos_le[200005][105];
bool pos_ri[200005][105];
int posB[200005];
bool posW[200005];

std::string solve_puzzle(std::string s, std::vector<int> c)
{
    s='_'+s+'_';
    n=s.size();
    for(int i=0; i<n; i++)
    {
        if(i) brw[i]=brw[i-1];
        if(s[i]=='_') brw[i]++;
    }
    k=c.size();
    for(int j=0; j<=n; j++)
    {
        if(s[j]=='X') break;
        pos_le[j][k]=1;
    }
    pos_ri[n][k]=1;
    for(int j=n-1; j>=0; j--)
    {
        if(s[j]=='X') break;
        pos_ri[j][k]=1;
    }
    for(int i=0; i<k; i++)
    {
        for(int j=1; j+c[i]<n; j++)
        {
            if(i && !pos_le[j-1][i-1]) continue;
            if(!i && !pos_le[j-1][k]) continue;
            if(brw[j+c[i]-1]-brw[j-1]) continue;
            if(s[j+c[i]]=='X') continue;
            pos_le[j+c[i]][i]=1;
            for(int t=j+c[i]+1; t<n && s[t]!='X'; t++, j++) pos_le[t][i]=1;
        }
    }
    for(int i=k-1; i>=0; i--)
    {
        for(int j=n-c[i]-1; j>=1; j--)
        {
            if(!pos_ri[j+c[i]][i+1]) continue;
            if(brw[j+c[i]-1]-brw[j-1]) continue;
            if(s[j-1]=='X') continue;
            pos_ri[j-1][i]=1;
            for(int t=j-2; t>=0 && s[t]!='X'; t--, j--) pos_ri[t][i]=1;
        }
    }
    for(int i=0; i<k; i++)
    {
        for(int j=1; j+c[i]<n; j++)
        {
            if(brw[j+c[i]-1]-brw[j-1]) continue;
            if(i==0 && !pos_le[j-1][k]) continue;
            if(i && !pos_le[j-1][i-1]) continue;
            if(!pos_ri[j+c[i]][i+1]) continue;
            posB[j]++;
            posB[j+c[i]]--;
        }
    }
    for(int j=1; j<=n; j++)
    {
        for(int i=0; i<=k; i++)
        {
            if(i && pos_le[j][i-1] && pos_ri[j][i]) posW[j]=1;
            if(!i && pos_le[j][k] && pos_ri[j][i]) posW[j]=1;
        }
    }
    for(int j=1; j<=n; j++)
    {
        posB[j]+=posB[j-1];
        if(posB[j] && posW[j]) s[j]='?';
        else if(posB[j]) s[j]='X';
        else if(posW[j]) s[j]='_';
    }
    return s.substr(1, n-2);
}

• 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