Submission #101968

#	Time	Username	Problem	Language	Result	Execution time	Memory
101968		baluteshih	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2071 ms	79708 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];
deque<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;k<=s.size()+1;++k,++t)
    	{
    		if(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=s.size()-sum;j>=0;--j)
    	{
    		int k=j+c[i]+1;
    		if(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++])
    {
    	for(int j=sum;j<=s.size()+1;++j)
    	{
    		for(int k=j-c[i-1]-1,t=j;k>=0;--k,--t)
    		{
    			if(t>0&&s[t-1]=='X') break;
    			if(Qb[k+c[i-1]]-Qb[k]>0) continue;
    			if(dp[k][i-1])
    			{
    				dp[j][i]=1;
    				if(rdp[j][i]) b[j]=1,++w[k+1],--w[k+c[i-1]+1];
				}
			}
		}
	}
    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:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k=s.size()-sum+c[i]+2,t=s.size()-sum;k<=s.size()+1;++k,++t)
                                                   ~^~~~~~~~~~~~
paint.cpp:57:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<=s.size()+1;++i)
              ~^~~~~~~~~~~~
paint.cpp:59:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i>0&&i<=s.size()&&s[i-1]=='X') break;
           ~^~~~~~~~~~
paint.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<=c.size();sum+=c[i++])
                 ~^~~~~~~~~~
paint.cpp:65:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j=sum;j<=s.size()+1;++j)
                    ~^~~~~~~~~~~~
paint.cpp:79: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