Submission #417360

#	Time	Username	Problem	Language	Result	Execution time	Memory
417360		TLP39	Paint By Numbers (IOI16_paint)	C++14	100 / 100	573 ms	85168 KiB

paint

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

int n,m;
int stat[200010];
int len[101]={};
bool all_front[200010][101],all_back[200010][101],one_front[200010][101],one_back[200010][101];
int streak_front[200010]={},streak_back[200010]={};

void solve_one_front(int x,int y)
{
    if(!x && !y)
    {
        one_front[0][0]=true;
        return;
    }
    if(!y)
    {
        one_front[x][0]=((one_front[x-1][0]) & (stat[x]!=1));
        return;
    }
    if(streak_front[x]<len[y])
    {
        one_front[x][y]=false;
        return;
    }
    if(x==len[y])
    {
        one_front[x][y]=(y==1);
        return;
    }
    one_front[x][y]=((stat[x-len[y]]!=1) & all_front[x-len[y]-1][y-1]);
    return;
}

void solve_front(int x,int y)
{
    solve_one_front(x,y);
    if(!x)
    {
        all_front[x][y]=(!y);
        return;
    }
    if(stat[x]==2)
    {
        all_front[x][y]=all_front[x-1][y];
        return;
    }
    if(stat[x]==1)
    {
        all_front[x][y]=one_front[x][y];
        return;
    }
    all_front[x][y]=all_front[x-1][y] || one_front[x][y];
    return;
}

void solve_one_back(int x,int y)
{
    if((x==n+1) && (y==m+1))
    {
        one_back[n+1][m+1]=true;
        return;
    }
    if(y==m+1)
    {
        one_back[x][y]=((one_back[x+1][y]) & (stat[x]!=1));
        return;
    }
    if(streak_back[x]<len[y])
    {
        one_back[x][y]=false;
        return;
    }
    if(n+1-x==len[y])
    {
        one_back[x][y]=(y==m);
        return;
    }
    one_back[x][y]=((stat[x+len[y]]!=1) & all_back[x+len[y]+1][y+1]);
    return;
}

void solve_back(int x,int y)
{
    solve_one_back(x,y);
    if(x==n+1)
    {
        all_back[x][y]=(y==m+1);
        return;
    }
    if(stat[x]==2)
    {
        all_back[x][y]=all_back[x+1][y];
        return;
    }
    if(stat[x]==1)
    {
        all_back[x][y]=one_back[x][y];
        return;
    }
    all_back[x][y]=all_back[x+1][y] || one_back[x][y];
    return;
}

int lp[200010];

bool test_white(int x)
{
    if(stat[x]==2) return true;
    if(stat[x]==1) return false;
    for(int i=0;i<=m;i++) if(all_front[x-1][i] && all_back[x+1][i+1]) {return true;}
    return false;
}
void longest_placed(int x)
{
    if(x<=n && stat[x]==1) return;
    if(x==n+1)
    {
        if(one_front[n][m]) lp[n+1]=len[m];
        return;
    }
    for(int i=0;i<=m;i++)
    {
        if(one_front[x-1][i] && all_back[x+1][i+1])
        {
            lp[x]=max(lp[x],len[i]);
        }
    }
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
    n=s.size();
    m=c.size();
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            all_front[i][j]=false;
            all_back[i][j]=false;
            one_front[i][j]=false;
            one_back[i][j]=false;
        }
    }
    for(int i=n;i>0;i--)
    {
        if(s[i-1]=='.') stat[i]=0;
        else if(s[i-1]=='X') stat[i]=1;
        else stat[i]=2;
    }
    for(int i=1;i<=n;i++)
    {
        streak_front[i]=(stat[i]!=2? streak_front[i-1]+1:0);
    }
    for(int i=n;i>=1;i--)
    {
        streak_back[i]=(stat[i]!=2? streak_back[i+1]+1:0);
    }
    for(int i=1;i<=m;i++)
    {
        len[i]=c[i-1];
    }
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            solve_front(i,j);
        }
    }
    for(int i=n+1;i>=1;i--)
    {
        for(int j=m+1;j>=1;j--)
        {
            solve_back(i,j);
        }
    }
    int res[200010]={};
    int cou[200010]={};
    for(int i=1;i<=n;i++)
    {
        if(test_white(i)) res[i]|=2;
    }
    for(int i=1;i<=n;i++) lp[i]=-1;
    for(int i=1;i<=n+1;i++)
    {
        longest_placed(i);
        if(lp[i]<0) continue;
        cou[i]--;
        cou[i-lp[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        cou[i]+=cou[i-1];
        if(cou[i]) res[i]|=1;
    }
    string ss;
    for(int i=1;i<=n;i++)
    {
        if(res[i]==1) ss.push_back('X');
        else if(res[i]==2) ss.push_back('_');
        else ss.push_back('?');
    }
    return ss;
}

• 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