Submission #205428

#	Time	Username	Problem	Language	Result	Execution time	Memory
205428		oko	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2092 ms	365264 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
#include <vector>
#include <string>
#include <cstdio>
#include <cassert>
using namespace std;
string a;
vector<int>k;
int dp[200050][150][3],wt[200050],bk[200050];
int f(int x,int y,int cl)
{
    if(x==a.size()-1)
    {
        if(y==k.size())return 1;
        else return 0;
    }
    if(dp[x][y][cl]!=-1)return dp[x][y][cl];
    int ans=0,cnt=0;
    if(cl==0)
    {
        if(a[x+1]=='X'&&y!=k.size())ans=max(ans,f(x+1,y,1));
        if(a[x+1]=='_')ans=max(ans,f(x+1,y,0));
        if(a[x+1]=='.')
        {
            if(y!=k.size())ans=max(ans,f(x+1,y,1));
            ans=max(ans,f(x+1,y,0));
        }
        return dp[x][y][cl]=ans;
    }
    for(int i=x; i<a.size(); i++)
    {
        if(a[i]=='_')break;
        cnt++;
        if(cnt==k[y]&&a[i+1]!='X')ans=max(ans,f(i+1,y+1,0));
    }
    return dp[x][y][cl]=ans;
}
string solve_puzzle(string s,vector<int> c)
{
    memset(dp,-1,sizeof dp);
    a=s,k=c;
    a.push_back('_');
    if(a[0]!='X')f(0,0,0);
    if(a[0]!='_')f(0,0,1);
    multiset<int>ms;
    for(int i=0; i<a.size(); i++)
    {
        for(int j=0; j<=k.size(); j++)
        {
            if(dp[i][j][1]==1)ms.insert(i+k[j]-1);
            if(dp[i][j][0]==1)wt[i]=1;
        }
        if(a[i]=='_')ms.clear();
        if(ms.size())
        {
            while(*ms.begin()<i)
            {
                ms.erase(ms.begin());
                if(ms.size()==0)break;
            }
        }
        if(ms.size())bk[i]=1;
    }
    string aa=a;
    for(int i=0;i<a.size();i++)
    {
        if(aa[i]!='.')continue;
        if(wt[i]+bk[i]==2)
        {
            aa[i]='?';
            continue;
        }
        if(wt[i])aa[i]='_';
        else aa[i]='X';
    }
    aa.erase(--aa.end());
    return aa;
}

Compilation message (stderr)

paint.cpp: In function 'int f(int, int, int)':
paint.cpp:13:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(x==a.size()-1)
        ~^~~~~~~~~~~~
paint.cpp:15:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(y==k.size())return 1;
            ~^~~~~~~~~~
paint.cpp:22:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(a[x+1]=='X'&&y!=k.size())ans=max(ans,f(x+1,y,1));
                         ~^~~~~~~~~~
paint.cpp:26:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(y!=k.size())ans=max(ans,f(x+1,y,1));
                ~^~~~~~~~~~
paint.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=x; i<a.size(); i++)
                  ~^~~~~~~~~
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++)
                  ~^~~~~~~~~
paint.cpp:49:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<=k.size(); j++)
                      ~^~~~~~~~~~
paint.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<a.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