Submission #63627

#	Time	Username	Problem	Language	Result	Execution time	Memory
63627		MKopchev	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1330 ms	108476 KiB

paint

/*
#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42,kmax=1e2+4;
string inp;
int n;
int white[nmax],black[nmax];
bool can[nmax][2];//0->white, 1->black
int mem[nmax][kmax];
int m,SZ[kmax];
int add[nmax],add_white[nmax];
bool rec(int pos,int which)
{
    //cout<<pos<<" "<<which<<endl;
    if(pos>n)return which>m;
    if(which>m)
    {
        if(black[n]!=black[pos-1])return 0;
        add_white[pos]++;
        add_white[n+1]--;
        return 1;
    }
    if(mem[pos][which]!=-1)return mem[pos][which];
    if(pos+SZ[which]-1>n)return 0;
    if(inp[pos]=='_')
    {
        mem[pos][which]=rec(pos+1,which);
        return mem[pos][which];
    }
    if(inp[pos]=='X')
    {
        if(white[pos+SZ[which]-1]-white[pos-1])return 0;//there is white
        if(inp[pos+SZ[which]]=='X')return 0;
        else mem[pos][which]=rec(pos+SZ[which]+1,which+1);
        if(mem[pos][which])
        {
        if(inp[pos+SZ[which]]=='.')can[pos+SZ[which]][0]=1;
        add[pos]++;
        add[pos+SZ[which]]--;
        }
        return mem[pos][which];
    }
    //inp[pos]=='.'
    bool wh=0,bl=0;
    if(rec(pos+1,which))
    {
        wh=1;
        can[pos][0]=1;
    }
    if(white[pos+SZ[which]-1]-white[pos-1]==0)
    {
        if(inp[pos+SZ[which]]=='X')bl=0;
        else bl=rec(pos+SZ[which]+1,which+1);
        if(bl)
        {
        if(inp[pos+SZ[which]]=='.')can[pos+SZ[which]][0]=1;
        add[pos]++;
        add[pos+SZ[which]]--;
        }
    }
    mem[pos][which]=bl|wh;
    return mem[pos][which];
}
string solve_puzzle(string s, int k, int c[])
{
memset(mem,-1,sizeof(mem));
inp=s;
n=inp.size();
inp=" "+inp+"W";
m=k;
for(int i=1;i<=k;i++)
    SZ[i]=c[i-1];
int w=0,b=0;
for(int i=1;i<=n;i++)
{
    if(inp[i]=='X')b++;
    if(inp[i]=='_')w++;
    white[i]=w;
    black[i]=b;
}
assert(rec(1,1));

int now=0,W=0;;
for(int i=1;i<=n;i++)
{
    now=now+add[i];
    W=W+add_white[i];
    if(now)can[i][1]=1;
    if(W)can[i][0]=1;
}
string outp="";
for(int i=1;i<=n;i++)
    if(inp[i]!='.')outp.push_back(inp[i]);
    else
    {
        if(can[i][0]&&can[i][1])outp.push_back('?');
        if(can[i][0]==0&&can[i][1])outp.push_back('X');
        if(can[i][0]&&can[i][1]==0)outp.push_back('_');
        if(can[i][0]==0&&can[i][1]==0)assert(0==1);
    }
return outp;
}
*/
/*
string s="..........";
//string s="........";
int k=2;
int c[2]={3,4};
int main()
{
cout<<solve_puzzle(s,k,c)<<endl;
}
*/
/*
string s=".X........";
//string s="........";
int k=1;
int c[1]={3};
int main()
{
cout<<solve_puzzle(s,k,c)<<endl;
}
*/
#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
const int nmax=2e5+42,kmax=1e2+4;
string inp;
int n;
int white[nmax],black[nmax];
bool can[nmax][2];//0->white, 1->black
int mem[nmax][kmax];
int m,SZ[kmax];
int add[nmax],add_white[nmax];
bool rec(int pos,int which)
{
    //cout<<pos<<" "<<which<<endl;
    if(pos>n)return which>m;
    if(which>m)
    {
        if(black[n]!=black[pos-1])return 0;
        add_white[pos]++;
        add_white[n+1]--;
        return 1;
    }
    if(mem[pos][which]!=-1)return mem[pos][which];
    if(pos+SZ[which]-1>n)return 0;
    if(inp[pos]=='_')
    {
        mem[pos][which]=rec(pos+1,which);
        return mem[pos][which];
    }
    if(inp[pos]=='X')
    {
        if(white[pos+SZ[which]-1]-white[pos-1])return 0;//there is white
        if(inp[pos+SZ[which]]=='X')return 0;
        else mem[pos][which]=rec(pos+SZ[which]+1,which+1);
        if(mem[pos][which])
        {
        if(inp[pos+SZ[which]]=='.')can[pos+SZ[which]][0]=1;
        add[pos]++;
        add[pos+SZ[which]]--;
        }
        return mem[pos][which];
    }
    //inp[pos]=='.'
    bool wh=0,bl=0;
    if(rec(pos+1,which))
    {
        wh=1;
        can[pos][0]=1;
    }
    if(white[pos+SZ[which]-1]-white[pos-1]==0)
    {
        if(inp[pos+SZ[which]]=='X')bl=0;
        else bl=rec(pos+SZ[which]+1,which+1);
        if(bl)
        {
        if(inp[pos+SZ[which]]=='.')can[pos+SZ[which]][0]=1;
        add[pos]++;
        add[pos+SZ[which]]--;
        }
    }
    mem[pos][which]=bl|wh;
    return mem[pos][which];
}
string solve_puzzle(string s, vector<int> c)
{
int k=c.size();
memset(mem,-1,sizeof(mem));
inp=s;
n=inp.size();
inp=" "+inp+"W";
m=k;
for(int i=1;i<=k;i++)
    SZ[i]=c[i-1];
int w=0,b=0;
for(int i=1;i<=n;i++)
{
    if(inp[i]=='X')b++;
    if(inp[i]=='_')w++;
    white[i]=w;
    black[i]=b;
}
assert(rec(1,1));

int now=0,W=0;;
for(int i=1;i<=n;i++)
{
    now=now+add[i];
    W=W+add_white[i];
    if(now)can[i][1]=1;
    if(W)can[i][0]=1;
}
string outp="";
for(int i=1;i<=n;i++)
    if(inp[i]!='.')outp.push_back(inp[i]);
    else
    {
        if(can[i][0]&&can[i][1])outp.push_back('?');
        if(can[i][0]==0&&can[i][1])outp.push_back('X');
        if(can[i][0]&&can[i][1]==0)outp.push_back('_');
        if(can[i][0]==0&&can[i][1]==0)assert(0==1);
    }
return outp;
}

• 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