Submission #139919

#	Time	Username	Problem	Language	Result	Execution time	Memory
139919		SirCeness	Paint By Numbers (IOI16_paint)	C++14	90 / 100	2059 ms	98136 KiB

paint

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

#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000009
#define mod 1000000007
#define ppair(x); cerr << "(" << x.first << ", " << x.second << ")\n";
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
using namespace std;
typedef long long ll;

string s;
int pre[200005];
string ans;
vector<int> c;
vector<int> xarr;

int dp[200005][101];

int varmi(int l, int r){
	int ans = 0;
	if (l == 0) ans = pre[r];
	else ans = pre[r] - pre[l-1];
	if (ans > 0) return 1;
	else return 0;
}

void merge(int i, char c){
	if (ans[i] == '!') ans[i] = c;
	else if (ans[i] == '_' && c == 'X') ans[i] = '?';
	else if (ans[i] == 'X' && c == '_') ans[i] = '?';
	else if (ans[i] == '_' && c == '?') ans[i] = '?';
	else if (ans[i] == 'X' && c == '?') ans[i] = '?';
}

void update(int l, int r){
	xarr[l]++;
	if (r+1 < s.size()) xarr[r+1]--;
}

int f(int i, int k){
	//cout << "f(" << i << ", " << k << ")" << endl;
	if (i >= s.size()) return (k == c.size());
	if (dp[i][k] != -1) return dp[i][k];
	int ans = 0;
	if (k != c.size() && i+c[k] > s.size()) return dp[i][k] = 0;	
	if (k < c.size() && (varmi(i, c[k]+i-1) == 0) && (c[k]+i == s.size() || s[i+c[k]] != 'X')){
		ans = f(i+c[k]+1, k+1);
		if (ans){
			update(i, i+c[k]-1);
			merge(i+c[k], '_');
		}
	}
	int ans2 = 0;
	if (s[i] != 'X') ans2 = f(i+1, k);
	if (ans2) merge(i, '_');
	return dp[i][k] = (ans|ans2);
}

string solve_puzzle(string S, vector<int> C) {
	c = C;
    s = S;
	int sum = 0;
	for (int i = 0; i < s.size(); i++){
		if (s[i] == '_') sum++;
		pre[i] = sum;
	}
	ans = "";
	for (int i = 0; i < s.size(); i++) ans += (s[i] == '_' ? '_' : '!');
	//for (int i = 0; i < s.size(); i++) if (s[i] == 'X') ans[i] = 'X';
	
	xarr.resize(s.size());
	for (int i = 0; i < s.size(); i++) xarr[i] = 0;
	
	for (int i = 0; i <= s.size()+1; i++) for (int j = 0; j <= c.size(); j++) dp[i][j] = -1;
	
	f(0, 0);
	
	if (xarr[0] > 0) merge(0, 'X');
	for (int i = 1; i < s.size(); i++){
		xarr[i] += xarr[i-1];
		if (xarr[i] > 0) merge(i, 'X');
	}
	
	return ans;
}

Compilation message (stderr)

paint.cpp: In function 'void update(int, int)':
paint.cpp:44:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (r+1 < s.size()) xarr[r+1]--;
      ~~~~^~~~~~~~~~
paint.cpp: In function 'int f(int, int)':
paint.cpp:49:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (i >= s.size()) return (k == c.size());
      ~~^~~~~~~~~~~
paint.cpp:49:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (i >= s.size()) return (k == c.size());
                             ~~^~~~~~~~~~~
paint.cpp:52:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (k != c.size() && i+c[k] > s.size()) return dp[i][k] = 0; 
      ~~^~~~~~~~~~~
paint.cpp:52:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (k != c.size() && i+c[k] > s.size()) return dp[i][k] = 0; 
                       ~~~~~~~^~~~~~~~~~
paint.cpp:53:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (k < c.size() && (varmi(i, c[k]+i-1) == 0) && (c[k]+i == s.size() || s[i+c[k]] != 'X')){
      ~~^~~~~~~~~~
paint.cpp:53:59: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (k < c.size() && (varmi(i, c[k]+i-1) == 0) && (c[k]+i == s.size() || s[i+c[k]] != 'X')){
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++){
                  ~~^~~~~~~~~~
paint.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++) ans += (s[i] == '_' ? '_' : '!');
                  ~~^~~~~~~~~~
paint.cpp:79:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++) xarr[i] = 0;
                  ~~^~~~~~~~~~
paint.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= s.size()+1; i++) for (int j = 0; j <= c.size(); j++) dp[i][j] = -1;
                  ~~^~~~~~~~~~~~~
paint.cpp:81:58: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= s.size()+1; i++) for (int j = 0; j <= c.size(); j++) dp[i][j] = -1;
                                                        ~~^~~~~~~~~~~
paint.cpp:86:20: 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