Submission #88134

#	Time	Username	Problem	Language	Result	Execution time	Memory
88134		Retro3014	Paint By Numbers (IOI16_paint)	C++17	100 / 100	470 ms	65620 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 chk2[MAX_N+10];
int chk1[MAX_N+10];
int arr[MAX_N+10];
int N, K;
string str, ans;
vector<int> v;
bool tf=false;

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

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' && (vst[x+1][y]?DP[x+1][y]:check(x+1, y))){
        chk2[x]=true;
        b=true;
    }
    if(y<K && x+v[y]<=N && (x+v[y]==N || str[x+v[y]]!='X') && arr[x]>=v[y] && (vst[x+v[y]+1][y+1]?DP[x+v[y]+1][y+1]:check(x+v[y]+1, y+1))){
        chk1[x]++;
        chk1[x+v[y]]--;
        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]);
    }
    arr[N]=0;
    for(int i=N-1; i>=0; i--){
        if(str[i]=='_'){
            arr[i]=0;
        }else{
            arr[i]=arr[i+1]+1;
        }
    }
    for(int i=0; i<c.size(); i++){
        v.push_back(c[i]);
    }
    check(0, 0);
    for(int i=0; i<N; i++){
        if(i!=0)    chk1[i]+=chk1[i-1];
        if(chk1[i]>0){
            if(chk2[i]){
                ans.push_back('?');
            }
            else{
                ans.push_back('X');
            }
        }
        else{
            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:65:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<s.size(); i++){
                  ~^~~~~~~~~
paint.cpp:76: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: 10 / 10