Submission #1131899

#TimeUsernameProblemLanguageResultExecution timeMemory
1131899t9unkubjPaint By Numbers (IOI16_paint)C++20
100 / 100
302 ms247852 KiB
#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
*/
const int N=2e5+1;
const int K=100+1;
int dp[2][N][K];
int dp2[N][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]=='_');
    dp[0][0][0]=1;
    rep(i,n){
        if(s[i]!='X'){
            //使わない
            rep(j,k+1){
                if((dp[0][i][j]||dp[1][i][j])){
                    dp[0][i+1][j]=1;
                }
            }
        }
        rep(j,k){
            if(dp[0][i][j]!=1)continue;
            int V=i+c[j];
            //[i,V) を塗る
            if(V<=n&&pre[V]-pre[i]==0){
                dp[1][V][j+1]=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;
    DREP(i,n,1){
        rep(j,k+1){
            if(!dp2[i][j])continue;
            //使わない
            if(s[i-1]!='X')
            if(dp[0][i-1][j]|dp[1][i-1][j]){
                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[0][V][j-1]){
                        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)ok1[i+1]+=ok1[i];
    rep(i,n)ok2[i+1]+=ok2[i];
    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
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...