Submission #1131897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131897		t9unkubj	Paint By Numbers (IOI16_paint)	C++20	90 / 100	378 ms	589824 KiB

paint

#include "paint.h"

#include <cstdlib>
#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;
/*
dp[i][j][k]:=
i-1 まで使い追って c_j を次に使う
前に使ったのがk
*/
std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n=s.size();
    int k=c.size();
    vc<int>pre(n+1);
    rep(i,n)pre[i+1]=pre[i]+(s[i]=='_');
    vc<vc<vc<int>>>dp(n+1,vvc<int>(k+1,vc<int>(2)));
    dp[0][0][0]=1;
    rep(i,n){
        if(s[i]!='X'){
            //使わない
            rep(j,k+1){
                if((dp[i][j][0]||dp[i][j][1])){
                    dp[i+1][j][0]=1;
                }
            }
        }
        rep(j,k){
            if(dp[i][j][0]!=1)continue;
            int V=i+c[j];
            //[i,V) を塗る
            if(V<=n&&pre[V]-pre[i]==0){
                dp[V][j+1][1]=1;
            }
        }
    }
    assert(dp[n][k][0]||dp[n][k][1]);
    vc<vc<int>>dp2(n+1,vc<int>(k+1));
    vc<int>ok1(n+1);
    vc<int>ok2(n+1);
    dp2[n][k]=1;
    dbg(dp[5][1][0]);
    DREP(i,n,1){
        rep(j,k+1){
            if(!dp2[i][j])continue;
            //使わない
            if(s[i-1]!='X')
            if(dp[i-1][j][0]|dp[i-1][j][1]){
                dp2[i-1][j]=1;
                ok1[i-1]++;
                ok1[i]--;
            }
            //使う
            if(j){
                int V=i-c[j-1];
                //[V,i)を塗る
                if(V>=0&&pre[i]-pre[V]==0){
                    if(dp[V][j-1][0]){
                        if(V&&s[V-1]=='X')continue;
                        dp2[max(0,V-1)][j-1]=1;
                        if(V){
                            ok1[V-1]++;
                            ok1[V]--;
                        }
                        ok2[V]++;
                        ok2[i]--;
                    }
                }
            }
        }
    }
    rep(i,n+1)rep(j,k+1)dbg(i,j,dp2[i][j]);

    rep(i,n+1)rep(j,k+1)dbg(i,j,dp[i][j]);
    rep(i,n)ok1[i+1]+=ok1[i];
    rep(i,n)ok2[i+1]+=ok2[i];
    dbg(ok1,ok2);
    string res;
    rep(i,n){
        if(ok1[i]&&ok2[i])res+='?';
        else if(ok1[i])res+='_';
        else if(ok2[i])res+='X';
        else assert(0);
    }
    return res;
}
namespace judge{
    void run(){
        string s;
        cin>>s;
        int k;
        cin>>k;
        vc<int>c(k);
        rep(i,k)cin>>c[i];
        dbg(solve_puzzle(s,c));
    }
};
//int main(){judge::run();}
//g++ paint/paint.cpp -D t9unkubj
/*
.......... 
2 
3 4

........
2
3 4

.X._._....
2
3 1

.X........ 1 3

*/

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: 10 / 10
• Subtask 7: 0 / 10