Submission #240195

#	Time	Username	Problem	Language	Result	Execution time	Memory
240195		Fasho	Paint By Numbers (IOI16_paint)	C++14	100 / 100	748 ms	250948 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 ("in.txt","r",stdin);freopen ("out.txt","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,tutmac[N];
 
ll dp[200100][150];
 
string att,sss;
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);
	a=min(a,1ll);
	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);
	}
	b=min(1ll,b);
	// cout<<ind<<sp<<k<<sp<<a<<sp<<b<<endl;
	if(sss[ind]=='_')
	{
		tutb[ind]=max(tutb[ind],a);
		return dp[ind][k]=a;
	}
	if(b)
		tutb[ind+ar[k]]=max(tutb[ind],1ll);
	if(sss[ind]=='X')
	{
 
		// updateRange(1,0,n-1,ind,ind+ar[k]-1,b);
		// upd(1,0,n-1,ind,ind+ar[k]-1,b);
		if(b)
 		tutmac[ind]=max(tutmac[ind],ar[k]);
		return dp[ind][k]=b;
	}
	tutb[ind]=max(tutb[ind],a);
	// cout<<ind<<sp<<k<<sp<<a<<sp<<b<<endl;
	// if(b)
	// 	cout<<"X"<<sp<<ind<<sp<<k<<endl;
	// if(a)
	// 	cout<<"_"<<sp<<ind<<sp<<k<<endl;
	if(b)
	tutmac[ind]=max(tutmac[ind],ar[k]);
	// updateRange(1,0,n-1,ind,ind+ar[k]-1,b);
	// upd(1,0,n-1,ind,ind+ar[k]-1,b);
	if(ind==0 && b)
		flag=1;
 
	return dp[ind][k]=max(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));
	fo(i,0,n)
	{
		pref[i]=pref[i-1];
		if(sss[i]=='_')
			pref[i]++;
	}
	f(0,0);
	att.clear();
	ll flag=0;
	// fo(i,0,n-1)
	// 	cout<<tutmac[i];
	// 	cout<<endl;
	// // ll flag=0;
	// fo(i,0,n-1)
	// 	cout<<tutb[i];
	// 	cout<<endl;
	fo(i,0,n-1)
	{
		// ll x=query(1,0,n-1,i);
		ll x=0;
		flag=max(flag,tutmac[i]);
		if(flag>=1)
			x=1;
		flag--;
		if(flag<0)
			flag=0;
		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'+queryRange(1,0,n-1,0,0);
	// char a='0'+query(1,0,n-1,0);
	// cout<<queryRange(1,0,n-1,0,0)<<sp;
	// cout<<query(1,0,n-1,0)<<endl;
	// string b;
	// b.pb(a);
	// fo(i,1,12)
	// b.pb('a');
	// cout<<ar[0]<<endl;;
	// return b;
	// return "?????XXX?????";
	// char x='0'+tutmac[0];
	// if(ar[0]==1559)
	// 	att[0]=x;
    return att;
}
 
// #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() {
// 	fast2;
//     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:137:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(att.size()!=i+1)
      ~~~~~~~~~~^~~~~

• 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