Submission #837961

#	Time	Username	Problem	Language	Result	Execution time	Memory
837961		oscar1f	Paint By Numbers (IOI16_paint)	C++17	100 / 100	472 ms	102416 KiB

paint

#include<bits/stdc++.h>
#include "paint.h"

using namespace std;

const int MAX_VAL=200*1000+5,MAX_BLOCS=100+5;
int nbVal,nbBlocs;
vector<int> listeBloc;
int etatDeb[MAX_VAL];
int prochBlanc[MAX_VAL];
int memo[MAX_VAL][MAX_BLOCS];
int possiBlanc[MAX_VAL],possiNoir[MAX_VAL];
string rep;

int dyna(int pos,int idBloc) {
    if (pos>=nbVal) {
        if (pos==nbVal and idBloc==nbBlocs) {
            return 1;
        }
        else {
            return 0;
        }
    }
    if (memo[pos][idBloc]!=-1) {
        return memo[pos][idBloc];
    }
    memo[pos][idBloc]=0;
    int ans;
    if (etatDeb[pos]!=1) {
        ans=dyna(pos+1,idBloc);
        if (ans==1) {
            memo[pos][idBloc]=1;
            possiBlanc[pos]=1;
        }
    }
    if (idBloc<nbBlocs and pos+listeBloc[idBloc]-1<nbVal and prochBlanc[pos]>=pos+listeBloc[idBloc] 
        and (pos+listeBloc[idBloc]==nbVal or etatDeb[pos+listeBloc[idBloc]]!=1)) {
        ans=dyna(min(pos+listeBloc[idBloc]+1,nbVal),idBloc+1);
        if (ans==1) {
            memo[pos][idBloc]=1;
            possiNoir[pos]++;
            possiNoir[pos+listeBloc[idBloc]]--;
            possiBlanc[pos+listeBloc[idBloc]]++;
        }
    }
    //cout<<pos<<" "<<idBloc<<" : "<<memo[pos][idBloc]<<endl;
    return memo[pos][idBloc];
}

string solve_puzzle(string s,vector<int> c) {
    nbVal=s.size();
    listeBloc=c;
    nbBlocs=listeBloc.size();
    for (int i=0;i<nbVal;i++) {
        if (s[i]=='.') {
            etatDeb[i]=0;
        }
        if (s[i]=='X') {
            etatDeb[i]=1;
        }
        if (s[i]=='_') {
            etatDeb[i]=2;
        }
        //cout<<etatDeb[i]<<" ";
    }
    prochBlanc[nbVal]=nbVal;
    for (int i=nbVal-1;i>=0;i--) {
        prochBlanc[i]=prochBlanc[i+1];
        if (etatDeb[i]==2) {
            prochBlanc[i]=i;
        }
    }
    for (int i=0;i<MAX_VAL;i++) {
        for (int j=0;j<MAX_BLOCS;j++) {
            memo[i][j]=-1;
        }
    }
    dyna(0,0);
    for (int i=1;i<nbVal;i++) {
        possiNoir[i]+=possiNoir[i-1];
    }
    for (int i=0;i<nbVal;i++) {
        //cout<<i<<" : "<<possiNoir[i]<<" "<<possiBlanc[i]<<endl;
        if (etatDeb[i]!=0) {
            rep+=s[i];
        }
        else {
            if (possiBlanc[i]>0 and possiNoir[i]>0) {
                rep+='?';
            }
            else if (possiBlanc[i]>0) {
                rep+='_';
            }
            else if (possiNoir[i]>0) {
                rep+='X';
            }
        }
    }
    return rep;
}

• 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