Submission #1232206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232206		inesfi	Paint By Numbers (IOI16_paint)	C++20	80 / 100	2092 ms	2736 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;

const int TAILLEMAXI=5002;
const int BLANC=0,NOIR=1,RIEN=2;
int n,k;
vector<int> couleurs;
vector<int> taille;
int cumu[TAILLEMAXI];
int memo[TAILLEMAXI][102];

void init(){
    for (int j=0;j<=n;j++){
        cumu[j]=0;
        for (int l=0;l<=k;l++){
            memo[j][l]=-1;
        }
    }
    for (int j=0;j<n;j++){
        if (couleurs[j]==BLANC){
            cumu[j]++;
        }
        if (j!=0){
            cumu[j]+=cumu[j-1];
        }
    }
}

int dp(int ec,int cb){
    if (ec==n+1){
        if (cb==k){
            return 1;
        }
        return 0;
    }
    if (memo[ec][cb]!=-1){
        return memo[ec][cb];
    }
    if (ec==n){
        if (cb==k){
            memo[ec][cb]=1;
            return 1;
        }
        memo[ec][cb]=0;
        return 0;
    }
    if (cb==k){
        if (couleurs[ec]==NOIR){
            memo[ec][cb]=0;
            return 0;
        }
        memo[ec][cb]=dp(ec+1,cb);
        return memo[ec][cb];
    }
    if (couleurs[ec]==BLANC){
        memo[ec][cb]=dp(ec+1,cb);
        return memo[ec][cb];
    }
    if (couleurs[ec]==NOIR){
        if (ec+taille[cb]>n){
            memo[ec][cb]=0;
            return 0;
        }
        if ((ec==0 and cumu[ec+taille[cb]-1]!=0) or (ec!=0 and cumu[ec+taille[cb]-1]-cumu[ec-1]!=0) 
        or (ec+taille[cb]<n and couleurs[ec+taille[cb]]==NOIR)){
            memo[ec][cb]=0;
            return 0;
        }
        memo[ec][cb]=dp(ec+taille[cb]+1,cb+1);
        return memo[ec][cb];
    }
    int r=0;
    r=max(r,dp(ec+1,cb));
    if (ec+taille[cb]<=n){
        if (!(ec==0 and cumu[ec+taille[cb]-1]!=0) and !(ec!=0 and cumu[ec+taille[cb]-1]-cumu[ec-1]!=0) 
        and !(ec+taille[cb]<n and couleurs[ec+taille[cb]]==NOIR)){
            r=max(r,dp(ec+taille[cb]+1,cb+1));
        }
    }
    memo[ec][cb]=r;
    return r;
}

string solve_puzzle (string s, vector<int> c) {
    n=s.size();
    k=c.size();
    taille=c;
    for (int i=0;i<n;i++){
        if (s[i]=='.'){
            couleurs.push_back(RIEN);
        }
        else if (s[i]=='X'){
            couleurs.push_back(NOIR);
        }
        else {
            couleurs.push_back(BLANC);
        }
    }
    string rep="";
    for (int i=0;i<n;i++){
        if (couleurs[i]==RIEN){
            bool okblanc=false,oknoir=false;
            couleurs[i]=BLANC;
            init();
            if (dp(0,0)==1){
                okblanc=true;
            }
            /*if (i==2){
                for (int j=0;j<=n;j++){
                    cout<<j<<" ";
                    for (int l=0;l<=k;l++){
                        cout<<memo[j][l]<<" ";
                    }
                    cout<<endl;
                }
            }*/
            couleurs[i]=NOIR;
            init();
            if (dp(0,0)==1){
                oknoir=true;
            }
            //cout<<okblanc<<" "<<oknoir<<endl;
            if (okblanc and oknoir){
                rep.push_back('?');
            }
            else if (okblanc){
                rep.push_back('_');
            }
            else {
                rep.push_back('X');
            }
            couleurs[i]=RIEN;
        }
        else {
            rep.push_back(s[i]);
        }
    }
    return rep;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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