제출 #240188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
240188		Fasho	Paint By Numbers (IOI16_paint)	C++14	0 / 100	131 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 ("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;
 
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)
{
	// push(ind,l,r);
	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);
	// tree[ind]=tree[ind*2]+tree[ind*2+1];
}
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=max(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(b,1ll);
	// 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')
	{
 
		// 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]=min(tutmac[ind],ar[k]);
		return dp[ind][k]=b;
	}
	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));
	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();
	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;
	tutb[0]=min(tutb[0],1ll);
	char x='0'+tutb[0];
	if(ar[0]==1559)
		att.pb(x);
	fo(i,0,n-2)
	{
		// 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?????";
	// cout<<tutb[0]<<sp<<tutmac[0]<<endl;
    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;
// }

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:188: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