Submission #380650

#	Time	Username	Problem	Language	Result	Execution time	Memory
380650		denkendoemeer	Paint By Numbers (IOI16_paint)	C++14	100 / 100	342 ms	44936 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
bool dp[210005][105],ok[210005][105];
int sum[210005];
int c1[210005],c2[210005];
string solve_puzzle(string s,vector<int>c)
{
    int i;
    for(i=0;i<s.size();i++){
        sum[i+1]+=sum[i];
        if (s[i]=='_')
            sum[i+1]++;
    }
    int n=c.size(),j;
    dp[0][0]=1;
    for(i=0;i<s.size();i++)
        for(j=0;j<=n;j++){
            if (dp[i][j]==0)
                continue;
            if (s[i]!='X')
                dp[i+1][j]=1;
            if (j<n){
                int st=i,dr=i+c[j];
                int nex;
                if (j==n-1)
                    nex=dr;
                else
                    nex=dr+1;
                if (nex<=s.size() && sum[dr]-sum[st]==0 && (j==n-1 || s[dr]!='X'))
                    dp[nex][j+1]=1;
            }
        }
    ok[s.size()][n]=1;
    for(i=s.size()-1;i>=0;i--)
        for(j=0;j<=n;j++){
            if (dp[i][j]==0)
                continue;
            if (s[i]!='X'){
                if (ok[i+1][j])
                    ok[i][j]=1,c2[i]=1;
            }
            if (j<n){
                int st=i,dr=i+c[j];
                int nex;
                if (j==n-1)
                    nex=dr;
                else
                    nex=dr+1;
                if (nex<=s.size() && sum[dr]-sum[st]==0 && (j==n-1 || s[dr]!='X')){
                    if (ok[nex][j+1]){
                        ok[i][j]=1;
                        c1[st]++;
                        c1[dr]--;
                        if (j!=n-1)
                            c2[dr]=1;
                    }
                }
            }
        }
    for(i=0;i<s.size();i++){
        c1[i+1]+=c1[i];
    }
    string ans;
    for(i=0;i<s.size();i++){
        if (c2[i] && c1[i])
            ans+='?';
        else
            if (c2[i])
                ans+='_';
            else
                if (c1[i])
                    ans+='X';
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:10:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(i=0;i<s.size();i++){
      |             ~^~~~~~~~~
paint.cpp:17:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(i=0;i<s.size();i++)
      |             ~^~~~~~~~~
paint.cpp:30:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |                 if (nex<=s.size() && sum[dr]-sum[st]==0 && (j==n-1 || s[dr]!='X'))
      |                     ~~~^~~~~~~~~~
paint.cpp:50:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |                 if (nex<=s.size() && sum[dr]-sum[st]==0 && (j==n-1 || s[dr]!='X')){
      |                     ~~~^~~~~~~~~~
paint.cpp:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(i=0;i<s.size();i++){
      |             ~^~~~~~~~~
paint.cpp:65:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(i=0;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: 10 / 10