제출 #1232350

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232350		inesfi	Paint By Numbers (IOI16_paint)	C++20	0 / 100	0 ms	320 KiB

paint

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

const int TAILLEMAXI=200*1000+2,KMAXI=102;
const int BLANC=0,NOIR=1,RIEN=2;
int n,k;
vector<int> couleurs;
vector<int> taille;
int cumu[TAILLEMAXI];
int memo[TAILLEMAXI][KMAXI];
int okblanc[TAILLEMAXI],oknoir[TAILLEMAXI];

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);
        okblanc[ec]=max(okblanc[ec],memo[ec][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);
        if (memo[ec][cb]==1){
            oknoir[ec]++;
            oknoir[ec+taille[cb]]--;
            okblanc[ec+taille[cb]]=1;
        }
        return memo[ec][cb];
    }
    int r=0;
    r=max(r,dp(ec+1,cb));
    okblanc[ec]=max(r,okblanc[ec]);
    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));
            if (dp(ec+taille[cb]+1,cb+1)==1){
                oknoir[ec]++;
                oknoir[ec+taille[cb]]--;
                okblanc[ec+taille[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);
        }
    }
    init();
    dp(0,0);
    string rep="";
    for (int i=0;i<n;i++){
        if (i!=0){
            oknoir[i]+=oknoir[i-1];
        }
        if (couleurs[i]==RIEN){
            if (okblanc[i]>=1 and oknoir[i]>=1){
                rep.push_back('?');
            }
            else if (okblanc[i]>=1){
                rep.push_back('_');
            }
            else {
                rep.push_back('X');
            }
        }
        else {
            rep.push_back(s[i]);
        }
        cout<<okblanc[i]<<" "<<oknoir[i]<<endl;
    }
    return rep;
}

컴파일 시 표준 에러 (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: 0 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10