Submission #101898

#	Time	Username	Problem	Language	Result	Execution time	Memory
101898		baluteshih	Paint By Numbers (IOI16_paint)	C++14	32 / 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];

string solve_puzzle(string s,vector<int> c)
{
	string ans;
	ans.resize(s.size());
	int sum=c.back();
    for(int i=0;i<=s.size()+1;++i)
		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)
    	{
    		for(int k=s.size()+1;k>j+c[i];--k)
    			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)
	{
		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=0;k<j-c[i-1];++k)
    			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:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<=s.size()+1;++i)
                 ~^~~~~~~~~~~~
paint.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<=s.size()+1;++i)
              ~^~~~~~~~~~~~
paint.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<=c.size();sum+=c[i++])
                 ~^~~~~~~~~~
paint.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j=sum;j<=s.size()+1;++j)
                    ~^~~~~~~~~~~~
paint.cpp:50: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: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10