Submission #878390

#	Time	Username	Problem	Language	Result	Execution time	Memory
878390		HuyQuang_re_Zero	Paint By Numbers (IOI16_paint)	C++14	100 / 100	265 ms	125368 KiB

paint

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "paint.h"
using namespace std;
bool l[200005][105],r[200005][105];
int sum_end[200005][105],n,m,i,j,len[105];
string solve_puzzle(string s,vector <int> c)
{
    n=s.size(); s=" "+s;
    for(int x:c) len[++m]=x;

    int last=n+1;
    r[n+1][m+1]=1;
    for(i=n;i>=1;i--)
    {
        if(s[i]=='_') last=i;
        for(j=m+1;j>=1;j--)
        {
            if(s[i]!='X') r[i][j]=r[i+1][j];
            if(last-i>=len[j] && j<=m)
            {
                int ok=(i+len[j]+1<n+2 ? (r[i+len[j]+1][j+1] && s[i+len[j]]!='X') : r[i+len[j]][j+1]);
               // if(i==4 && j==1) cerr<<i+len[j]+1<<'\n';
                r[i][j]|=ok;
            }
        }
    }
    last=0;
    l[0][0]=1;
    for(i=1;i<=n;i++)
    {
        if(s[i]=='_') last=i;
        for(j=0;j<=m;j++)
        {
            if(s[i]!='X') l[i][j]=l[i-1][j];
            if(i-last>=len[j] && j>0)
            {
                int ok=(i-len[j]-1>=0 ? (l[i-len[j]-1][j-1] && s[i-len[j]]!='X') : l[i-len[j]][j-1]);
                l[i][j]|=ok;
                sum_end[i][j]=(ok && (i==n ? r[i+1][j+1] : (s[i+1]!='X' && r[i+2][j+1])));
            }
            sum_end[i][j]+=sum_end[i-1][j];
        }
    }
   // cerr<<sum_end[n][2]-sum_end[n-1][2];
    string res="";
    for(i=1;i<=n;i++)
    {
        int okw=0,okb=0;
        if(s[i]!='X')
            for(j=0;j<=m;j++)
            {
                okw|=(l[i-1][j] && r[i+1][j+1]);
               // if(i==3 && okw) cerr<<j<<'\n';
            }
        if(s[i]!='_')
            for(j=1;j<=m;j++)
                okb|=(sum_end[min(n,i+len[j]-1)][j]-sum_end[i-1][j]>0);
        if(okw && okb) res+="?";
        else if(okw) res+='_';
        else res+='X';
    }
    return res;
}
/*
int main()
{
    freopen("paint.inp","r",stdin);
    freopen("paint.out","w",stdout);
    string s; cin>>s;
    vector <int> c;
    int x;
    while(cin>>x) c.push_back(x);
    cout<<solve_puzzle(s,c);
}
*/

• 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