Submission #239909

#	Time	Username	Problem	Language	Result	Execution time	Memory
239909		Fasho	Paint By Numbers (IOI16_paint)	C++14	0 / 100	118 ms	235384 KiB

paint

#include <bits/stdc++.h>
#define N 300005
#define ll long long int 	
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
#define ull unsigned long long int
#include "paint.h"
using namespace std;

ll n,m,ar[N],sum,t,tut[N],tree[6*N],tutb[N],lazy[6*N],pref[N];

ll dp[200100][150];

string ans,s;

void push(int ind,int l,int r)
{
	ll x=lazy[ind];
	tree[ind]+=x;
	lazy[ind]=0;
	if(l==r)
		return;
	lazy[ind*2]+=x;
	lazy[ind*2+1]+=x;
}

ll query(ll ind,ll l,ll r,ll a)
{
	if(l>a || r<a)
		return 0;
	push(ind,l,r);
	if(l==r)
		return tree[ind];
	int mid=(l+r)/2;
	ll x=query(ind*2,l,mid,a);
	ll y=query(ind*2+1,mid+1,r,a);
	return max(x,y);
}
void upd(int ind,int l,int r,int a,int b,ll val)
{
	if(l>b || r<a)
		return;
	push(ind,l,r);
	if(l>=a && r<=b)
	{
		lazy[ind]+=val;
		push(ind,l,r);
		return;
	}
	int mid=(l+r)/2;
	upd(ind*2,l,mid,a,b,val);
	upd(ind*2+1,mid+1,r,a,b,val);
}

ll f(int ind,int k)
{
	if(ind>n)
		return 0;
	if(ind==n && k==m)
	{
		// cerr<<"hello"<<endl;
		return 1;
	}
	if(k>m)
		return 0;
	if(ind==n)
		return 0;
	// cerr<<ind<<sp<<k<<endl;

	if(dp[ind][k]!=-1)
		return dp[ind][k];
	ll a=0;
	if(s[ind]!='X')
		a=f(ind+1,k);
	ll x=0;
	ll b=0;
	if(ind>0)
		x=pref[ind-1];

	if(ind+ar[k]<=n && pref[ind+ar[k]-1]-x==0 && s[ind+ar[k]]!='X' && s[ind]!='_')
	{
		if(ind+ar[k]==n)
			b=f(ind+ar[k],k+1);
		else
			b=f(ind+ar[k]+1,k+1);
	}
	cout<<ind<<sp<<k<<sp<<a<<sp<<b<<endl;
	if(s[ind]=='_')
	{
		tutb[ind]=a;
		return dp[ind][k]=a;
	}
	if(b)
		tutb[ind+ar[k]]=1;
	if(s[ind]=='X')
	{

		upd(1,0,n-1,ind,ind+ar[k]-1,b);
		return dp[ind][k]=b;
	}
	tutb[ind]=a;
	// if(b)
	// 	cout<<"X"<<sp<<ind<<sp<<k<<endl;
	// if(a)
	// 	cout<<"_"<<sp<<ind<<sp<<k<<endl;
	upd(1,0,n-1,ind,ind+ar[k]-1,b);
	return dp[ind][k]=a+b;


}

string solve_puzzle(string ss,vector<int> c) 
{
	m=c.size();
	fo(i,0,m-1)
		ar[i]=c[i];
	n=ss.size();
	s=ss;
	memset(dp,-1,sizeof(dp));
	fo(i,0,n)
	{
		pref[i]=pref[i-1];
		if(s[i]=='_')
			pref[i]++;
	}
	f(0,0);
	fo(i,0,n-1)
	{
		ll x=query(1,0,n-1,i);
		ll y=tutb[i];
		ans.pb('?');
		if(x && !y)
			ans[i]='X';
		if(!x && y)
			ans[i]='_';
	}
    return ans;
}

// vector<int> v;
// int main()
// {
// 	fast;
// 	cin>>s>>n;
// 	fo(i,1,n)
// 	{
// 		int a;
// 		cin>>a;
// 		v.pb(a);
// 	}
// 	cout<<solve_puzzle(s,v);


// }

• 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