Submission #522960

#	Time	Username	Problem	Language	Result	Execution time	Memory
522960		Deepesson	Paint By Numbers (IOI16_paint)	C++17	100 / 100	618 ms	39768 KiB

paint

#include <bits/stdc++.h>
#define UNSOLVED 0
#define VALID 1
#define INVALID 2
#include "paint.h"
#define MAXK 105
#define MAX 505000
unsigned char existe[MAX][MAXK];
int pbranco[MAX];
std::string u;
int get(int x){
    if(x<0)return 0;
    return pbranco[x];
}
int seg(int l,int r){
    return get(r)-get(l-1);
}
std::vector<int> blocos;
bool pode[MAX][2];
int rangeblacko[MAX];
unsigned char dp(int pos,int k){
    if(pos>u.size())return INVALID;
    if(pos==u.size()){
        if(k==blocos.size())return VALID;
        return INVALID;
    }
    if(existe[pos][k]!=UNSOLVED)return existe[pos][k];
    bool ok=false;
    ///Branco ou misterio
    if(u[pos]=='.'||u[pos]=='_'){
        if(dp(pos+1,k)==VALID){
            ok=true;
            pode[pos][0]=1;
        }
    }
    ///Preto ou misterio
    if(k<blocos.size()&&(u[pos]=='.'||u[pos]=='X')){
        if(pos+blocos[k]<=u.size())
        if((!seg(pos,pos+blocos[k]-1))&&((pos+blocos[k]==u.size())||(u[pos+blocos[k]]!='X'))&&(dp(std::min(pos+blocos[k]+1,(int)u.size()),k+1)==VALID)){
            rangeblacko[pos]++;
            rangeblacko[pos+blocos[k]]--;
            pode[pos+blocos[k]][0]=1;
            ok=true;
        }
    }
    if(ok)return existe[pos][k]=VALID;
    return existe[pos][k]=INVALID;
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
    u=s;
    blocos=c;
    int soma=0;
    for(int i=0;i!=u.size();++i){
        if(s[i]=='_')++soma;
        pbranco[i]=soma;
    }
    assert(dp(0,0)==VALID);
    std::string resp;
    int toc=0;
    for(int i=0;i!=u.size();++i){
        toc+=rangeblacko[i];
        if(pode[i][0]&&(toc)){
            resp+="?";
        }else if(pode[i][0])resp+="_";else resp+="X";
    }
    return resp;
}

Compilation message (stderr)

paint.cpp: In function 'unsigned char dp(int, int)':
paint.cpp:22:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     if(pos>u.size())return INVALID;
      |        ~~~^~~~~~~~~
paint.cpp:23:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     if(pos==u.size()){
      |        ~~~^~~~~~~~~~
paint.cpp:24:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         if(k==blocos.size())return VALID;
      |            ~^~~~~~~~~~~~~~~
paint.cpp:37:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     if(k<blocos.size()&&(u[pos]=='.'||u[pos]=='X')){
      |        ~^~~~~~~~~~~~~~
paint.cpp:38:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         if(pos+blocos[k]<=u.size())
      |            ~~~~~~~~~~~~~^~~~~~~~~~
paint.cpp:39:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         if((!seg(pos,pos+blocos[k]-1))&&((pos+blocos[k]==u.size())||(u[pos+blocos[k]]!='X'))&&(dp(std::min(pos+blocos[k]+1,(int)u.size()),k+1)==VALID)){
      |                                           ~~~~~~~~~~~~~^~~~~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0;i!=u.size();++i){
      |                 ~^~~~~~~~~~
paint.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i!=u.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