Submission #65262

#	Time	Username	Problem	Language	Result	Execution time	Memory
65262		FedericoS	Paint By Numbers (IOI16_paint)	C++14	80 / 100	67 ms	66856 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <assert.h>
#include <iostream>
using namespace std;

int N,K;
int C[10005];
string DP[10005][105];
string S;

string F(int i, int j){

    if(C[j]>=i+2 or i<0)
        return "z";

    if(DP[i][j]!="asd")
        return DP[i][j];

    for(int p=i;p>i-C[j];p--)
        if(S[p]=='_'){
            DP[i][j]="z";
            return "z";
        }

    string s(i+1,'0');

    if(j==0){

        for(int p=i-C[j];p>=0;p--)
            if(S[p]=='X'){
                DP[i][j]="z";
                return "z";
            }

        for(int p=0;p<=i-C[j];p++)
            s[p]='_';
        for(int p=i-C[j]+1;p<=i;p++)
            s[p]='X';

        DP[i][j]=s;
        return s;

    }
    else{

        bool flag=false;

        for(int p=i-C[j];p>=0;p--){

            if(S[p]=='X')
                break;

            if(F(p-1,j-1)!="z"){

                if(!flag){

                    s=F(p-1,j-1);
                    for(int q=p;q<=i-C[j];q++)
                        s.push_back('_');
                    flag=true;

                }
                else{

                    string r;

                    r=F(p-1,j-1);
                    for(int q=p;q<=i-C[j];q++)
                        r.push_back('_');

                    assert(s.size()==r.size());

                    for(int q=0;q<=i-C[j];q++)
                        if(s[q]!=r[q])
                            s[q]='.';

                }
            }
        }

        if(!flag){
            DP[i][j]="z";
            return "z";
        }

        for(int p=i-C[j]+1;p<=i;p++)
            s.push_back('X');

        DP[i][j]=s;
        return s;

    }

}

string solve_puzzle(string s_, vector<int> c_) {

    N=s_.size();
    K=c_.size();

    assert(N<=100 and K<=100);

    S=s_;
    for(int i=0;i<N;i++)
        C[i]=c_[i];


    for(int i=0;i<N;i++)
        for(int j=0;j<K;j++)
            DP[i][j]="asd";

    //for(int i=0;i<N;i++)for(int j=0;j<K;j++)cout<<i<<" "<<j<<" "<<F(i,j)<<"\n";

    string A,B;
    bool flag=false;

    for(int i=0;i<N;i++)
        if(F(i,K-1)!="z"){

            B=(F(i,K-1));
            bool g=true;

            for(int p=B.size();p<N;p++)
                if(S[p]=='X')
                    g=false;
            if(!g)
                continue;

            while(B.size()<N)
                B.push_back('_');

            if(!flag){
                A=B;
                flag=true;
            }
            else
                for(int i=0;i<N;i++)
                    if(A[i]!=B[i])
                        A[i]='.';
        }

    for(int i=0;i<N;i++)
        if(A[i]=='.')
            A[i]='?';

    return A;

}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:130:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(B.size()<N)
                   ~~~~~~~~^~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10