Submission #61038

#	Time	Username	Problem	Language	Result	Execution time	Memory
61038		Tenuun	Paint By Numbers (IOI16_paint)	C++17	100 / 100	1677 ms	66676 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>

using namespace std;

int b[200001], w[200001], x[200003], y[200003];
bool vis[200001][101]={false}, dp[200001][101]={false};
string s;
int n;
vector<int>c;
void pre(){
	memset(x, 0, sizeof x);
	memset(y, 0, sizeof y);
    b[0]=w[0]=0;
    if(s[0]=='_') w[0]++;
    else if(s[0]=='X') b[0]++;
    for(int i=1; i<=s.length(); i++){
    	b[i]=b[i-1];
    	w[i]=w[i-1];
    	if(s[i]=='_') w[i]++;
    	else if(s[i]=='X') b[i]++;
    }
}

bool solve(int u, int ind){
	if(ind==n){
		if(u==0){
			if(b[s.length()-1]==0){
				y[u]++;
				return true;
			}
			else return false;
		}
		if(b[s.length()-1]-b[u-1]==0){
			y[u]++;
			return true;
		}
		return false;
	}
	if(u>=s.length() && ind<n) return false;
	if(vis[u][ind]) return dp[u][ind];
	vis[u][ind]=true;
	int t=c[ind];
	if(u==0){
		if(u+t-1<s.length() && w[u+t-1]==0 && s[u+t]!='X'){
			if(solve(u+t+1, ind+1)==true){
				x[u]++;
				x[u+t]--;
				y[u+t]++;
				y[u+t+1]--;
				dp[u][ind]=true;
			}
		}
	}
	else{
		if(u+t-1<s.length() && w[u+t-1]-w[u-1]==0 && s[u+t]!='X'){
			if(solve(u+t+1, ind+1)==true){
				x[u]++;
				x[u+t]--;
				y[u+t]++;
				y[u+t+1]--;
				dp[u][ind]=true;
			}
		}
	}
	if(s[u]!='X' && solve(u+1, ind)==true){
		y[u]++;
		y[u+1]--;
		dp[u][ind]=true;
	}
	return dp[u][ind];
}

string solve_puzzle(std::string ss, std::vector<int> c) {
    s=ss;
    ::c=c;
    n=c.size();
    pre();
    solve(0, 0);
    for(int i=1; i<ss.length(); i++){
    	x[i]=x[i]+x[i-1];
    	y[i]=y[i]+y[i-1];
    }
    string res;
    for(int i=0; i<ss.length(); i++){
    	if(x[i] && y[i]) res+='?';
    	else if(x[i]) res+='X';
    	else res+='_';
    }
    return res;
}

Compilation message (stderr)

paint.cpp: In function 'void pre()':
paint.cpp:17:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<=s.length(); i++){
                  ~^~~~~~~~~~~~
paint.cpp: In function 'bool solve(int, int)':
paint.cpp:40:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(u>=s.length() && ind<n) return false;
     ~^~~~~~~~~~~~
paint.cpp:45:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(u+t-1<s.length() && w[u+t-1]==0 && s[u+t]!='X'){
      ~~~~~^~~~~~~~~~~
paint.cpp:56:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(u+t-1<s.length() && w[u+t-1]-w[u-1]==0 && s[u+t]!='X'){
      ~~~~~^~~~~~~~~~~
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:80:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<ss.length(); i++){
                  ~^~~~~~~~~~~~
paint.cpp:85:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<ss.length(); 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: 10 / 10