Submission #87869

#	Time	Username	Problem	Language	Result	Execution time	Memory
87869		Retro3014	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2061 ms	49764 KiB

paint

#include "paint.h"

#include <string>
#include <vector>

using namespace std;

#define MAX_N 200000
#define MAX_K 100

bool vst[MAX_N+10][MAX_K+10];
bool DP[MAX_N+10][MAX_K+10];
bool chk1[MAX_N+1], chk2[MAX_N+1];
int N, K;
string str, ans;
vector<int> v;

bool put(int x, int y){
    if(x+y>N){
        return false;
    }
    for(int i=x; i<x+y; i++){
        if(str[i]=='_'){
            return false;
        }
    }
    if(x+y==N || str[x+y]!='X')    return true;
    return false;
}

bool check(int x, int y){
    if(vst[x][y]){
        return DP[x][y];
    }
    vst[x][y]=true;
    bool b=false;
    if(x>=N){
        if(y==K)    b=true;
        DP[x][y]=b;
        return b;
    }
    if(str[x]!='X' && check(x+1, y)){
        chk2[x]=true;
        b=true;
    }
    if(y<K && put(x, v[y]) && check(x+v[y]+1, y+1)){
        for(int i=x; i<x+v[y]; i++){
            chk1[i]=true;
        }
        chk2[x+v[y]]=true;
        b=true;
    }
    DP[x][y]=b;
    return b;
}

string solve_puzzle(string s, vector<int> c) {
    N=(int)s.size(); K=(int)c.size();
    for(int i=0; i<s.size(); i++){
        str.push_back(s[i]);
    }
    for(int i=0; i<c.size(); i++){
        v.push_back(c[i]);
    }
    check(0, 0);
    for(int i=0; i<N; i++){
        if(chk1[i]){
            if(chk2[i]){
                ans.push_back('?');
            }
            else{
                ans.push_back('X');
            }
        }
        else if(chk2[i]){
            ans.push_back('_');
        }
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<s.size(); i++){
                  ~^~~~~~~~~
paint.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<c.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