Submission #131521

#	Time	Username	Problem	Language	Result	Execution time	Memory
131521		mahmoudbadawy	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2057 ms	98740 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>

using namespace std;

string ss;
vector<int> arr;
int n,k;
int ok[2*100005];
int ansb[2*100005],answ[2*100005];
int mem[2*100005][105];
string ans;

int go(int ind,int ind2)
{
    if(ind>=n&&ind2>=k)
        return 1;
    if(ind>=n)
        return 0;
    if(mem[ind][ind2]!=-1)
        return mem[ind][ind2];
    if(ind2>=k)
    {
        if(ss[ind]=='X')
            return mem[ind][ind2]=0;
        bool ok=go(ind+1,ind2);
        if(ok) answ[ind]++;
        return mem[ind][ind2]=ok;
    }
    bool okk=0;
    if(ind+arr[ind2]<=n&&ok[ind+arr[ind2]]-ok[ind]==arr[ind2]&&(ind+arr[ind2]>=n||ss[ind+arr[ind2]]!='X'))
    {
        bool ok2=go(ind+arr[ind2]+1,ind2+1);
        if(ok2)
        {
            ansb[ind]++;
            answ[ind+arr[ind2]]++;
            ansb[ind+arr[ind2]]--;
        }
        okk|=ok2;
    }
    if(ss[ind]!='X')
    {
        bool ok2=go(ind+1,ind2);
        if(ok2)
            answ[ind]++;
        okk|=ok2;
    }
    return mem[ind][ind2]=okk;
}

std::string solve_puzzle(std::string s, std::vector<int> c) {
    ss=s; arr=c;
    n=s.size();
    k=c.size();
    ans=string(n,'?');
    int i,j;
    for(i=0;i<=n;i++)
        for(j=0;j<=k;j++)
            mem[i][j]=-1;
    for(i=1;i<=n;i++)
    {
        ok[i]=(s[i-1]=='X'||s[i-1]=='.');
        ok[i]+=ok[i-1];
    }
    go(0,0);
    for(i=1;i<s.size();i++)
    {
        ansb[i]+=ansb[i-1];
    }
    for(i=0;i<n;i++)
    {
        if(ansb[i]&&answ[i])
            ans[i]='?';
        else if(ansb[i])
            ans[i]='X';
        else
            ans[i]='_';
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:68:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1;i<s.size();i++)
             ~^~~~~~~~~

• 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: 0 / 10