Submission #101903

#	Time	Username	Problem	Language	Result	Execution time	Memory
101903		baluteshih	Paint By Numbers (IOI16_paint)	C++14	59 / 100	4 ms	512 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],Qb[200005];
int mus[200005],rmus[200005];

string solve_puzzle(string s,vector<int> c)
{
	string ans;
	ans.resize(s.size());
	for(int i=1;i<=s.size()+1;++i)
	{
		Qb[i]=Qb[i-1]+(s[i-1]=='_');
		if(i<=s.size()&&s[i-1]=='X'&&mus[i]==0)
		{
			mus[i]=mus[i-1]+1;
			for(int j=i+1;j<i+c[mus[i-1]];++j)
				mus[j]=mus[i];
		}
		else mus[i]=mus[i-1];
	}
	for(int i=0;i<=s.size()+1;++i)
		rmus[i]=c.size();
	for(int i=s.size();i>=0;--i)
	{
		if(i>0&&s[i-1]=='X'&&rmus[i]==c.size())
		{
			rmus[i]=rmus[i+1]-1;
			for(int j=i-1;j>i-c[rmus[i-1]];--j)
				rmus[j]=rmus[i];
		}
		else rmus[i]=rmus[i+1];
	}
	int sum=c.back();
    for(int i=s.size()+1;i>=0;--i)
	{
		if(rmus[i]<c.size()) break;
		rdp[i][c.size()]=1;
	}
    for(int i=c.size()-1;i>=0;sum+=c[--i]+1)
    	for(int j=s.size()-sum;j>=0;--j)
    	{
    		if(j>0&&s[j-1]=='X') continue;
    		if(rmus[j]<i) break; 
    		for(int k=s.size()+1;k>j+c[i];--k)
    		{
    			if(Qb[k-1]-Qb[k-c[i]-1]>0) continue;
    			if(rdp[k][i+1]) rdp[j][i]=1;
			}
    		//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)
    	{
    		if(s[j-1]=='X') continue;
    		if(mus[j]>i) break;
    		for(int k=0;k<j-c[i-1];++k)
    		{
    			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:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<=s.size()+1;++i)
              ~^~~~~~~~~~~~
paint.cpp:28:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i<=s.size()&&s[i-1]=='X'&&mus[i]==0)
      ~^~~~~~~~~~
paint.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<=s.size()+1;++i)
              ~^~~~~~~~~~~~
paint.cpp:40:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i>0&&s[i-1]=='X'&&rmus[i]==c.size())
                        ~~~~~~~^~~~~~~~~~
paint.cpp:51:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(rmus[i]<c.size()) break;
      ~~~~~~~^~~~~~~~~
paint.cpp:69:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<=s.size()+1;++i)
              ~^~~~~~~~~~~~
paint.cpp:71:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i>0&&i<=s.size()&&s[i-1]=='X') break;
           ~^~~~~~~~~~
paint.cpp:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<=c.size();sum+=c[i++])
                 ~^~~~~~~~~~
paint.cpp:76:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j=sum;j<=s.size()+1;++j)
                    ~^~~~~~~~~~~~
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: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10