Submission #140283

#	Time	Username	Problem	Language	Result	Execution time	Memory
140283		MrBrionix	Paint By Numbers (IOI16_paint)	C++14	100 / 100	672 ms	99840 KiB

paint

//#include "paint.h"

#include <vector>
#include <string>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include<bits/stdc++.h>
using namespace std;

int dp[200005][105],us[200005][105];
vector<int> info;
int sumb[200005],sumn[200005],tmp,solb[200005],soln[200005],tmp2;
string v,sol;

int f(int pos,int num){
    
    if(dp[pos][num]!=-1)return dp[pos][num];
    
    
    if(pos>=v.size() && num==info.size())return 1;
    if(pos>=v.size() && num!=info.size())return 0;
    if(num==info.size() && (sumn[v.size()]-sumn[pos])!=0)return 0;
    if(num==info.size() && (sumn[v.size()]-sumn[pos])==0){
        solb[pos]++;
        solb[v.size()]--;
        //cout<<pos<<" "<<v.size()<<endl;
        return 1;
    }
    
    
    int opz=0;
    
    if(v[pos]!='X'){
        if(f(pos+1,num)==1){
            solb[pos]++;
            solb[pos+1]--;
            opz=1;
        }
    }
    
    if((pos+info[num]-1)<v.size() && ((pos+info[num])==v.size() || v[(pos+info[num])]!='X') && (sumb[(pos+info[num])]-sumb[pos])==0){
    
        if(f(pos+info[num]+1,num+1)==1){
            soln[pos]++;
            soln[pos+info[num]]--;
            solb[pos+info[num]]++;
            solb[pos+info[num]+1]--;
            opz=1;
        }
    }
    
   //cout<<pos<<" "<<num<<" vale "<<opz<<endl;
    
    return dp[pos][num]=opz;
}

string solve_puzzle(string s, vector<int> c){
    
    info=c;
    for(int i=0;i<200005;i++)for(int j=0;j<105;j++)dp[i][j]=-1;
    
    tmp=0;
    for(int i=0;i<s.size();i++){
        sumb[i]=tmp;
        if(s[i]=='_')tmp++;
    }
    sumb[s.size()]=tmp;
    
    tmp=0;
    for(int i=0;i<s.size();i++){
        sumn[i]=tmp;
        if(s[i]=='X')tmp++;
    }
    sumn[s.size()]=tmp;
    
    v=s;
    
    f(0,0);
    
/*
..........
2 3 4
*/

    
    tmp=tmp2=0;
    
    for(int i=0;i<s.size();i++){
        tmp+=solb[i];
        tmp2+=soln[i];
        
        if(tmp>0 && tmp2>0)sol.push_back('?');
        else{
            if(tmp>0)sol.push_back('_');
            else sol.push_back('X');
        }
    }
    
    return sol;
}
/*
const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];

int main() {
    assert(1 == scanf("%s", buf));
    std::string s = buf;
    int c_len;
    assert(1 == scanf("%d", &c_len));
    std::vector<int> c(c_len);
    for (int i = 0; i < c_len; i++) {
        assert(1 == scanf("%d", &c[i]));
    }
    std::string ans = solve_puzzle(s, c);


    printf("%s\n", ans.data());
    return 0;
}
*/

Compilation message (stderr)

paint.cpp: In function 'int f(int, int)':
paint.cpp:21:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(pos>=v.size() && num==info.size())return 1;
        ~~~^~~~~~~~~~
paint.cpp:21:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(pos>=v.size() && num==info.size())return 1;
                         ~~~^~~~~~~~~~~~~
paint.cpp:22:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(pos>=v.size() && num!=info.size())return 0;
        ~~~^~~~~~~~~~
paint.cpp:22:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(pos>=v.size() && num!=info.size())return 0;
                         ~~~^~~~~~~~~~~~~
paint.cpp:23:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(num==info.size() && (sumn[v.size()]-sumn[pos])!=0)return 0;
        ~~~^~~~~~~~~~~~~
paint.cpp:24:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(num==info.size() && (sumn[v.size()]-sumn[pos])==0){
        ~~~^~~~~~~~~~~~~
paint.cpp:42:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if((pos+info[num]-1)<v.size() && ((pos+info[num])==v.size() || v[(pos+info[num])]!='X') && (sumb[(pos+info[num])]-sumb[pos])==0){
        ~~~~~~~~~~~~~~~~~^~~~~~~~~
paint.cpp:42:54: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if((pos+info[num]-1)<v.size() && ((pos+info[num])==v.size() || v[(pos+info[num])]!='X') && (sumb[(pos+info[num])]-sumb[pos])==0){
                                       ~~~~~~~~~~~~~~~^~~~~~~~~~
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.size();i++){
                 ~^~~~~~~~~
paint.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.size();i++){
                 ~^~~~~~~~~
paint.cpp:89:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int 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