Submission #206950

#	Time	Username	Problem	Language	Result	Execution time	Memory
206950		autumn_eel	Paint By Numbers (IOI16_paint)	C++14	100 / 100	438 ms	46968 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;

bool dp[210000][110],ok[210000][110];
int sum[210000];
int cX[210000],c_[210000];

string solve_puzzle(string s,vector<int>c){
	rep(i,s.size()){
		sum[i+1]+=sum[i];
		if(s[i]=='_')sum[i+1]++;
	}
	int K=c.size();
	dp[0][0]=1;
	rep(i,s.size())rep(j,K+1){
		if(!dp[i][j])continue;
		if(s[i]!='X'){
			dp[i+1][j]=1;
		}
		if(j<K){
			int l=i,r=i+c[j];
			int nx=(j==K-1?r:r+1);
			if(nx<=s.size()&&sum[r]-sum[l]==0&&(j==K-1||s[r]!='X')){
				dp[nx][j+1]=1;
			}
		}
	}
	ok[s.size()][K]=1;
	for(int i=s.size()-1;i>=0;i--)rep(j,K+1){
		if(!dp[i][j])continue;
		if(s[i]!='X'){
			if(ok[i+1][j])ok[i][j]=1,c_[i]=1;
		}
		if(j<K){
			int l=i,r=i+c[j];
			int nx=(j==K-1?r:r+1);
			if(nx<=s.size()&&sum[r]-sum[l]==0&&(j==K-1||s[r]!='X')){
				if(ok[nx][j+1]){
					ok[i][j]=1;
					cX[l]++;cX[r]--;
					if(j!=K-1)c_[r]=1;
				}
			}
		}
	}
	rep(i,s.size()){
		cX[i+1]+=cX[i];
	}
	string ans;
	rep(i,s.size()){
		if(c_[i]&&cX[i])ans+="?";
		else if(c_[i])ans+="_";
		else if(cX[i])ans+="X";
	}
	assert(s.size()==ans.size());
	return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:3:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
paint.cpp:11:2: note: in expansion of macro 'rep'
  rep(i,s.size()){
  ^~~
paint.cpp:3:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
paint.cpp:17:2: note: in expansion of macro 'rep'
  rep(i,s.size())rep(j,K+1){
  ^~~
paint.cpp:25:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(nx<=s.size()&&sum[r]-sum[l]==0&&(j==K-1||s[r]!='X')){
       ~~^~~~~~~~~~
paint.cpp:39:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(nx<=s.size()&&sum[r]-sum[l]==0&&(j==K-1||s[r]!='X')){
       ~~^~~~~~~~~~
paint.cpp:3:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
paint.cpp:48:2: note: in expansion of macro 'rep'
  rep(i,s.size()){
  ^~~
paint.cpp:3:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
paint.cpp:52:2: note: in expansion of macro 'rep'
  rep(i,s.size()){
  ^~~

• 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