Submission #135451

#	Time	Username	Problem	Language	Result	Execution time	Memory
135451		ckodser	Paint By Numbers (IOI16_paint)	C++14	80 / 100	2055 ms	39688 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=2e5+500;
const ll inf=1e9+900;
const ll maxk=100;

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

bool safnadasht(ll l,ll r){
    if(l<0 || gs.size()<=r)return 0;
    for(ll i=l;i<=r;i++)if(gs[i]=='_')return 0;
    return 1;
}
void make_dp(string s,vector<ll> c){
    gs=s;
    ll n=s.size();
    ll k=c.size();
    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];
string solve_puzzle(string s, vector<int> c) {
    return slowSolve(s,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];
	}
    }
    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);
	    }
	}
	cout<<j<<":";
	for(auto v:star)cout<<v<<' ';
	cout<<endl;

    }
    return s;
}

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