Submission #119039

#	Time	Username	Problem	Language	Result	Execution time	Memory
119039		TuGSGeReL	Paint By Numbers (IOI16_paint)	C++14	7 / 100	2 ms	384 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key
#define lb lower_bound
#define ub upper_bound

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
using pll = pair <ll, ll>;
using pii = pair <int, int>;

int dp[100001], wh[100001], rdp[100001];
string ans;

bool canx(int k, string s, vector <int> c) {
	int L, R, l = 1, r = k;
	
	while ( l + 1 < r ) {
		int mid = (l + r) / 2;
		
		if ( wh[k] - wh[mid - 1] )
			l = mid;
		
		else
			r = mid;
	}
	
	L = r;
	
	if ( wh[k] - wh[l - 1] == 0 )
		L--;
	
	l = k, r = s.size() - 1;
	
	while ( l + 1 < r ) {
		int mid = (l + r) / 2;
		
		if ( wh[mid] - wh[k - 1] )
			r = mid;
		
		else
			l = mid;
	}
	
	R = l;
	
	if ( wh[r] - wh[k - 1] == 0 )
		R++;
	
	if ( dp[max(L - 2, 0)] + dp[R + 2] >= c.size() ) {
		for (int i = 0; i < c.size(); i++)
			if ( c[i] <= R - L + 1 )
				if ( dp[max(L - 2, 0)] >= i && dp[R + 2] >= c.size() - i - 1 )
					return 1;
		
		return 0;
	} else {
		int S = 0;
		
		for (int i = dp[max(L - 2, 0)]; i < c.size() - dp[R + 2] - 1; i++) {
			S += c[i];
			
			if ( i != c.size() - dp[R + 2] - 2 )
				S++;
			
			if ( k == L + S - 1 )
				S++;
		}
		
		if ( S <= R - L + 1 )
			return 1;
		
		return 0;
	}
}

bool canw(int k, string s, vector <int> c) {
	if ( dp[k - 1] + rdp[k + 1] >= c.size() )
		return 1;
	
	return 0;
}

string solve_puzzle(string s, vector<int> c) {
	s = '0' + s;
	
	for (int i = 1; i < s.size(); i++) {
		wh[i] = wh[i - 1];

		if ( s[i] == '_' )
			wh[i]++;
	}
	
	for (int i = 1; i < s.size(); i++) {
		dp[i] = dp[i - 1];
		if ( s[i] == '_' ) {
			continue;
		} else {
			for (int j = 0; j < c.size();j++)
				if ( i >= c[j] && wh[i] - wh[i - c[j]] == 0 )
					if ( dp[max(i - c[j] - 1, 0)] >= j )
						dp[i] = max(dp[i], j + 1);
		}
	}
	
	for (int i = s.size() - 1; i > 0; i--)
	{
		rdp[i] = rdp[i + 1];
		if ( s[i] == '_' ) {
			continue;
		} else {
			for (int j = c.size() - 1; j >= 0; j--)
				if ( s.size() - 1 - i + 1 >= c[j] && wh[i + c[j] - 1] - wh[i - 1] == 0 )
					if ( rdp[i + c[j] + 1] >= c.size() - j - 1 )
						rdp[i] = max(rdp[i], (int)c.size() - j);
		}
	}
	
	for (int i = 1; i < s.size(); i++) {
		if ( s[i] == 'X' || s[i] == '_' )
			ans += s[i];
		else if ( canx(i, s, c) && canw(i, s, c) ) {
			ans += '?';
		} else if ( canx(i, s, c) )
			ans += 'X';
		else
			ans += '_';
	}
	
	return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool canx(int, std::__cxx11::string, std::vector<int>)':
paint.cpp:63:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if ( dp[max(L - 2, 0)] + dp[R + 2] >= c.size() ) {
       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
paint.cpp:64:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < c.size(); i++)
                   ~~^~~~~~~~~~
paint.cpp:66:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if ( dp[max(L - 2, 0)] >= i && dp[R + 2] >= c.size() - i - 1 )
                                    ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
paint.cpp:73:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = dp[max(L - 2, 0)]; i < c.size() - dp[R + 2] - 1; i++) {
                                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:76:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if ( i != c.size() - dp[R + 2] - 2 )
         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.cpp: In function 'bool canw(int, std::__cxx11::string, std::vector<int>)':
paint.cpp:91:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if ( dp[k - 1] + rdp[k + 1] >= c.size() )
       ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < s.size(); i++) {
                  ~~^~~~~~~~~~
paint.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < s.size(); i++) {
                  ~~^~~~~~~~~~
paint.cpp:112:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < c.size();j++)
                    ~~^~~~~~~~~~
paint.cpp:126:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if ( s.size() - 1 - i + 1 >= c[j] && wh[i + c[j] - 1] - wh[i - 1] == 0 )
paint.cpp:127:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if ( rdp[i + c[j] + 1] >= c.size() - j - 1 )
           ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
paint.cpp:132: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: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10