Submission #135468

#	Time	Username	Problem	Language	Result	Execution time	Memory
135468		ckodser	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1080 ms	112320 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
#include <cstdlib>

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll>

using namespace :: std;

const ll maxn=3e5+10;
const ll maxk=110;

bool dp[maxn][maxk];
bool dpf[maxn][maxk];
string gs;
ll pr[maxn];

bool safnadasht(ll l,ll r){
    if(l<0 || gs.size()<=r)return 0;
    if(l==0 && pr[r]!=0)return 0;
    if(pr[r]!=pr[l-1])return 0;
    return 1;
}
void make_dp(string s,vector<ll> c){
    gs=s;
    ll n=s.size();
    ll k=c.size();

    pr[0]=(s[0]=='_');
    for(ll i=1;i<n;i++){
	pr[i]=pr[i-1]+(s[i]=='_');
    }

    memset(dp,0,sizeof dp);
    memset(dpf,0,sizeof dpf);
    dp[0][0]=1;
    dpf[0][0]=1;
    for(ll i=1;i<=n;i++){
	for(ll j=0;j<=k;j++){
	    if(s[i-1]=='_'){
		dp[i][j]=0;
		dpf[i][j]=dpf[i-1][j]|dp[i-1][j];
	    }
	    else{
		if(j && safnadasht(i-c[j-1],i-1)){
		    dp[i][j]=dpf[i-c[j-1]][j-1];
		}
		if(s[i-1]=='.'){
		    dpf[i][j]|=dpf[i-1][j]|dp[i-1][j];
		}
	    }
	}
    }
}
bool valid(string s,vector<int> c){
    make_dp(s,c);
    ll n=s.size();
    ll k=c.size();

    return (dpf[n][k] || dp[n][k]);
}

string slowSolve(string s,vector<int> c){
    ll n=s.size();
    ll k=c.size();
    string ans=s;
    for(ll i=0;i<n;i++){
	if(s[i]=='.'){
	    s[i]='_';
	    bool q=valid(s,c);
	    s[i]='X';
	    bool w=valid(s,c);
	    if(q && !w){
		ans[i]='_';
	    }
	    if(!q && w){
		ans[i]='X';
	    }
	    if(w && q){
		ans[i]='?';
	    }
	    s[i]='.';
	}
    }
    return ans;
}

bool sdp[maxn][maxk];
bool sdpf[maxn][maxk];
ll prr[maxn];


string solve_puzzle(string s, vector<int> c) {
    make_dp(s,c);
    ll n=s.size();
    ll k=c.size();
    for(ll i=0;i<=n;i++){
	for(ll j=0;j<=k;j++){
	    sdp[i][j]=dp[i][j];
	    sdpf[i][j]=dpf[i][j];
	}
    }
    reverse(s.begin(),s.end());
    reverse(c.begin(),c.end());
    make_dp(s,c);
    reverse(s.begin(),s.end());
    reverse(c.begin(),c.end());
     
    for(ll j=0;j<k;j++){
	vector<ll> star;
	for(ll i=0;i<n;i++){
	    if(sdp[i+1][j+1] && n-1-i+c[j]>=0 && dp[n-1-i+c[j]][k-j]){
		star.pb(i);
	    }
	}
	for(auto v:star){
	    prr[v+1]--;
	    prr[v-c[j]+1]++;
	}
    }
    for(ll i=1;i<n;i++)prr[i]+=prr[i-1];
    string ans=s;
    for(ll i=0;i<n;i++){
	if(s[i]=='.'){
	    if(prr[i]==0){
		ans[i]='_';
		continue;
	    }
	    bool mish=0;
	    for(ll j=0;j<=k;j++){
		if(sdpf[i+1][j] && dpf[n-i][k-j]){
		    mish=1;
		}
	    }
	    if(mish){
		ans[i]='?';
	    }else{
		ans[i]='X';
	    }
	}
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool safnadasht(int, int)':
paint.cpp:24:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(l<0 || gs.size()<=r)return 0;
               ~~~~~~~~~^~~
paint.cpp: In function 'std::__cxx11::string slowSolve(std::__cxx11::string, std::vector<int>)':
paint.cpp:70:8: warning: unused variable 'k' [-Wunused-variable]
     ll k=c.size();
        ^

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