Submission #239969

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

paint

#include <bits/stdc++.h>
#define N 200005
#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],flag;

ll dp[200100][150];

string att,sss;

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);
	if(a<=mid)
		return x;
	else
		return y;
	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(sss[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 && sss[ind+ar[k]]!='X' && sss[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(sss[ind]=='_')
	{
		tutb[ind]=a;
		return dp[ind][k]=a;
	}
	if(b)
		tutb[ind+ar[k]]=1;
	if(sss[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);
	if(ind==0 && b)
		flag=1;

	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();
	sss=ss;
	memset(dp,-1,sizeof(dp));
	memset(tree,0,sizeof(tree));
	memset(lazy,0,sizeof(lazy));
	fo(i,0,n)
	{
		pref[i]=pref[i-1];
		if(sss[i]=='_')
			pref[i]++;
	}
	f(0,0);
	att.clear();
	fo(i,0,n-1)
	{
		ll x=query(1,0,n-1,i);
		ll y=tutb[i];
		if(x && !y)
			att.pb('X');
		if(!x && y)
			att.pb('_');
		if(att.size()!=i+1)
		att.pb('?');
	}
	// char a='0'+query(1,0,n-1,0);
	char a='0'+flag;
	string b;
	b.pb(a);
	fo(i,1,12)
	b.pb('a');
	// cout<<ar[0]<<endl;;
	return b;
	// return "?????XXX?????";
    return att;
}

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


// }
// #include "paint.h"

// #include <vector>
// #include <string>
// #include <cstdio>
// #include <cassert>

// const int S_MAX_LEN = 200 * 1000;
// char buf[S_MAX_LEN + 1];

// int main() {
//     assert(1 == scanf("%s", buf));
//     std::string s = buf;
//     int c_len;
//     assert(1 == scanf("%d", &c_len));
//     std::vector<int> c(c_len);
//     for (int i = 0; i < c_len; i++) {
//         assert(1 == scanf("%d", &c[i]));
//     }
//     std::string ans = solve_puzzle(s, c);


//     printf("%s\n", ans.data());
//     return 0;
// }

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:158:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(att.size()!=i+1)
      ~~~~~~~~~~^~~~~

• 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