Submission #101998

#	Time	Username	Problem	Language	Result	Execution time	Memory
101998		baluteshih	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1954 ms	168560 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define pb push_back
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define F first
#define S second
#define ET cout << "\n"
#define MP make_pair
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
int dp[200005][105],rdp[200005][105],w[200005],b[200005];
int Qb[200005],dq[200005];
 
string solve_puzzle(string s,vector<int> c)
{
	string ans;
	ans.resize(s.size());
	for(int i=1;i<=s.size();++i)
		Qb[i]=Qb[i-1]+(s[i-1]=='_');
	int sum=c.back();
    for(int i=s.size()+1;i>=0;--i)
	{
		if(i>0&&i<=s.size()&&s[i-1]=='X') break;
		rdp[i][c.size()]=1;
	}
    for(int i=c.size()-1;i>=0;sum+=c[--i]+1)
    {
    	int flag=0;
    	for(int k=s.size()-sum+c[i]+2,t=s.size()-sum+1;k<=s.size()+1;++k,++t)
    	{
    		if(t<=s.size()&&t>0&&s[t-1]=='X') break;
    		if(Qb[k-1]-Qb[k-c[i]-1]>0) continue;
    		if(rdp[k][i+1]) flag=1;
		}
    	for(int j=min(s.size()-sum,s.size()-c[i]);j>=0;--j)
    	{
    		int k=j+c[i]+1;
    		if(k>s.size()+1) continue;
    		if(j<=s.size()&&j>0&&s[j-1]=='X')
    			flag=0;
    		else if(Qb[k-1]-Qb[k-c[i]-1]<=0) 
    			flag|=rdp[k][i+1];
    		rdp[j][i]=flag;
    		//cout << "rdp[" << j << "][" << i+1 << "] = " << rdp[j][i+1] << "\n";
		}
	}

    sum=c[0];
	for(int i=0;i<=s.size()+1;++i)
	{
		if(i>0&&i<=s.size()&&s[i-1]=='X') break;
		dp[i][0]=1;
		if(rdp[i][0]) b[i]=1; 
	}
    for(int i=1;i<=c.size();sum+=c[i++]+1)
    {
    	int flag=0,t=0;
    	if(sum-c[i-1]-1>=0&&s[sum-1]!='X')
			for(int k=sum-c[i-1]-2,t=sum-1;k>=0;--k,--t)
			{
				if(t<=s.size()&&t>0&&s[t-1]=='X') break;
				if(Qb[k+c[i-1]]-Qb[k]>0) continue;
				if(dp[k][i-1])
					flag=1,dq[t++]=k;
			}
    	for(int j=max(sum,c[i-1]+1);j<=s.size()+1;++j)
    	{
    		int k=j-c[i-1]-1;
    		if(j<=s.size()&&j>0&&s[j-1]=='X')
				flag=0,t=0;
			else if(Qb[k+c[i-1]]-Qb[k]<=0) 
			{
				if(dp[k][i-1]) dq[t++]=k,flag=1;
			}
			if(rdp[j][i]&&flag)
			{
				dp[j][i]=1,b[j]=1;
				for(int p=0;p<t;++p)
					++w[dq[p]+1],--w[dq[p]+c[i-1]+1];
				t=0;
			}
		}
	}
    for(int i=1;i<=s.size();++i)
    {
    	w[i]+=w[i-1];
    	if(w[i]&&b[i]) ans[i-1]='?';
    	else if(b[i]) ans[i-1]='_';
    	else ans[i-1]='X';
	}
	return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<=s.size();++i)
              ~^~~~~~~~~~
paint.cpp:29:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i>0&&i<=s.size()&&s[i-1]=='X') break;
           ~^~~~~~~~~~
paint.cpp:35:54: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k=s.size()-sum+c[i]+2,t=s.size()-sum+1;k<=s.size()+1;++k,++t)
                                                     ~^~~~~~~~~~~~
paint.cpp:37:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(t<=s.size()&&t>0&&s[t-1]=='X') break;
          ~^~~~~~~~~~
paint.cpp:44:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(k>s.size()+1) continue;
          ~^~~~~~~~~~~
paint.cpp:45:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(j<=s.size()&&j>0&&s[j-1]=='X')
          ~^~~~~~~~~~
paint.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<=s.size()+1;++i)
              ~^~~~~~~~~~~~
paint.cpp:57:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i>0&&i<=s.size()&&s[i-1]=='X') break;
           ~^~~~~~~~~~
paint.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<=c.size();sum+=c[i++]+1)
                 ~^~~~~~~~~~
paint.cpp:67:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(t<=s.size()&&t>0&&s[t-1]=='X') break;
        ~^~~~~~~~~~
paint.cpp:72:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j=max(sum,c[i-1]+1);j<=s.size()+1;++j)
                                  ~^~~~~~~~~~~~
paint.cpp:75:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(j<=s.size()&&j>0&&s[j-1]=='X')
          ~^~~~~~~~~~
paint.cpp:90:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<=s.size();++i)
                 ~^~~~~~~~~~

• 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