Submission #241709

#	Time	Username	Problem	Language	Result	Execution time	Memory
241709		crossing0ver	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2099 ms	290360 KiB

paint

#include<bits/stdc++.h>
//#include "paint.h"
using namespace std;
int n;
int x[1000000],dpL[300000][102][2],dpR[300000][102][2],black[300000],L[2][300005],R[2][300005],white[300000];
vector<int> c;
void checkL(int pos,int k) {
	for (int i = 0; i < 2; i++) {
		if (x[pos] == 0 && i == 1) continue;
		if (x[pos] == 1 && i == 0) continue;
		if (i == 0) 
			dpL[pos][k][0] = (dpL[pos-1][k][0]|dpL[pos-1][k][1])|(c[k] == 0 && L[1][pos] == 0);
		if (i == 1) {
			if (pos - L[0][pos] < c[k] || c[k] == 0) {
				dpL[pos][k][1] = 0;
				continue;
			}
			dpL[pos][k][1] = dpL[pos - c[k]][k-1][0];
		}
	}
//	cout << pos << " " << k <<' ' << dpL[pos][k][1]<<'\n';
}
void checkR(int pos,int k) {
    //if (pos == 4 && k == 2) cout <<"hah"<<x[pos]<<' ';
	for (int i = 0; i < 2; i++) {
		if (x[pos] == 0 && i == 1) continue;
		if (x[pos] == 1 && i == 0) continue;
		if (i == 0) {
			dpR[pos][k][0] = (dpR[pos + 1][k][0]|dpR[pos+1][k][1])|(c[k] == 0 && R[1][pos] == n+1);
		}		
		if (i == 1) {
			if (pos + c[k] > R[0][pos] || c[k] == 0) {
			dpR[pos][k][1] = 0;
			continue;
			}
			dpR[pos][k][1] = dpR[pos + c[k]][k+1][0];
		//	if (pos == 4 && k == 2) cout <<"bla";
		}                                   
	}
}


string solve_puzzle(string s, vector<int> c1) {
	// preprocess
	s = "#" + s;
	n = (int)s.size() - 1;
	int k = c1.size();
	for (int i = 1; i <= n; i++) {
		if (s[i] == 'X') {
		x[i] = 1;
		L[0][i] = L[0][i-1];
		L[1][i] = R[1][i] = i;
	}                    
		else if (s[i] == '_') {
		x[i] = 0;        
		L[0][i] = R[0][i] = i;
		L[1][i] = L[1][i-1];
	}	                 
		else {            
		x[i] = 2;         
		L[0][i] = L[0][i-1];
	 	L[1][i] = L[1][i-1];
	}                    
	}                        
	R[0][n+1] = R[1][n+1] = n+1;
	for (int i = n; i > 0; i--) {
		if (s[i] == 'X')  
			R[0][i] = R[0][i+1];
		else if (s[i] == '_') R[1][i] = R[1][i+1];
		else {
			R[0][i] = R[0][i+1];
			R[1][i] = R[1][i+1];
		} 
	}
	//for (int i = 1; i <= n; i++) cout << L[1][i] <<" "<<R[1][i]<<'\n';
	c.push_back(0);

	for (int i : c1) c.push_back(i);
	k++;
	c.push_back(0);
	k++;
	
	// preprecessing done 
	dpL[0][0][0] = 1;
	dpR[n+1][k-1][0] = dpR[n+1][k][0] = 1;
	for (int i = 1;i <= n; i++) 
		for (int j = 0; j <= k-1; j++) 
			checkL(i,j);	
	//		cout << n <<'\n';
//	cout << k-1 <<' ';
	for (int i  = n; i > 0; i--)
	for (int j = k-1; j >= 0; j--) {
		checkR(i,j);
	}
//	cout << dpL[3][0][0] <<' '<<dpL[3][1][1] <<' '<<dpL[2][0][0];
	//	cout  << dpR[4][2][1] << ' ';
	for (int i = 1;i  <= n; i++) {
		for (int j = 0; j < k;j++) {
			if ((x[i] != 1) && (dpL[i][j][0] == 1 && dpR[i][j+1][0] == 1   )|| (x[i] == 0) )
				white[i] = 1;	
				if (j != 0)
			for (int e = i; e < min(i + c[j],n+1); e++)
			black[i] |= (dpL[e][j][1] & dpR[e+1][j+1][0]);
			if (x[i] == 1) black[i] = 1;
		}								
	}
	string ans;
	for (int i = 1; i <= n; i++) {
		if (white[i] && black[i]) ans += "?";
		else if (white[i]) ans+="_";
		else ans += "X";
	}	
    return ans;
}  /*
main() {
	string s; cin >> s;
	int n; cin >> n;
	vector<int> c1(n);
	for (int i = 0,j; i < n;i++){
		cin >> j;
		c1[i] = j;
	}
	cout << solve_puzzle(s,c1);
}*/
/* ..........
	2 3 4
	*/

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:99:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    if ((x[i] != 1) && (dpL[i][j][0] == 1 && dpR[i][j+1][0] == 1   )|| (x[i] == 0) )
        ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
paint.cpp:99:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if ((x[i] != 1) && (dpL[i][j][0] == 1 && dpR[i][j+1][0] == 1   )|| (x[i] == 0) )
    ^~
paint.cpp:101:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     if (j != 0)
     ^~

• 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