Submission #1131858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131858		t9unkubj	Paint By Numbers (IOI16_paint)	C++20	0 / 100	0 ms	320 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]:=
i-1 まで使い追って次につかうのが　j である状態になれるか
*/
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<int>>dp(n+1,vc<int>(k+1));
    vc<vc<pair<int,int>>>mae(n+1,vc<pair<int,int>>(k+1));
    dp[0][0]=1;
    rep(i,n){
        if(s[i]!='X'){
            rep(j,k+1){
                if(dp[i][j]&&dp[i+1][j]==0)dp[i+1][j]=1,mae[i+1][j]={i,j};
            }
        }
        rep(j,k){
            if(dp[i][j]!=1)continue;
            int V=i+c[j];
            dbg(i,j,V);
            //[i,V) を塗る
            if(V<=n&&pre[V]-pre[i]==0){
                if(dp[V][j+1]==0){
                    if(V+1<=n){
                        if(dp[V+1][j+1])continue;
                        dp[V+1][j+1]=1;
                        mae[V+1][j+1]={V,j+1};
                        dp[V][j+1]=2;
                        mae[V][j+1]={i,j};
                    }else{
                        dp[V][j+1]=1;
                        mae[V][j+1]={i,j};
                    }
                }
            }
        }
    }
    assert(dp[n][k]);
    int nn=n,kk=k;
    string res;
    while(nn){
        //黒で塗る
        if(mae[nn][kk].second!=kk){
            for(int i=mae[nn][kk].first+1;i<=nn;i++){
                res+='X';
            }
        }else{
            res+='_';
        }
        tie(nn,kk)=mae[nn][kk];
    }
    reverse(all(res));
    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

..._._....
3
3 1 4

.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: 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