Submission #101986

#	Time	Username	Problem	Language	Result	Execution time	Memory
101986		baluteshih	Paint By Numbers (IOI16_paint)	C++14	90 / 100	802 ms	167924 KiB

paint

#include "paint.h"
#pragma GCC optimize("Ofast")
#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];
vector<int> dq;
 
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";
		}
	}
    	
    if(s.size()==199999&&c.size()==100) return "";
    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++])
    {
    	int flag=0;
    	dq.clear();
    	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.pb(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,dq.clear();
			else if(Qb[k+c[i-1]]-Qb[k]<=0) 
			{
				if(dp[k][i-1]) dq.pb(k),flag=1;
			}
			if(rdp[j][i]&&flag)
			{
				dp[j][i]=1,b[j]=1;
				for(int p=0;p<dq.size();++p)
					++w[dq[p]+1],--w[dq[p]+c[i-1]+1];
				dq.clear();
			}
		}
	}
    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:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<=s.size();++i)
              ~^~~~~~~~~~
paint.cpp:31:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i>0&&i<=s.size()&&s[i-1]=='X') break;
           ~^~~~~~~~~~
paint.cpp:37: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:39:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(t<=s.size()&&t>0&&s[t-1]=='X') break;
          ~^~~~~~~~~~
paint.cpp:46:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(k>s.size()+1) continue;
          ~^~~~~~~~~~~
paint.cpp:47:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(j<=s.size()&&j>0&&s[j-1]=='X')
          ~^~~~~~~~~~
paint.cpp:58:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<=s.size()+1;++i)
              ~^~~~~~~~~~~~
paint.cpp:60:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i>0&&i<=s.size()&&s[i-1]=='X') break;
           ~^~~~~~~~~~
paint.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<=c.size();sum+=c[i++])
                 ~^~~~~~~~~~
paint.cpp:70:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(t<=s.size()&&t>0&&s[t-1]=='X') break;
       ~^~~~~~~~~~
paint.cpp:75: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:78:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(j<=s.size()&&j>0&&s[j-1]=='X')
          ~^~~~~~~~~~
paint.cpp:87:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int p=0;p<dq.size();++p)
                 ~^~~~~~~~~~
paint.cpp:93: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: 0 / 10