Submission #999361

#	Time	Username	Problem	Language	Result	Execution time	Memory
999361		ByeWorld	Paint By Numbers (IOI16_paint)	C++14	100 / 100	180 ms	209364 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int MAXN = 2e5+5;
const int MAXK = 105;
const int INF = 1e9+10;
typedef pair<int,int> pii;

/* idea:
	dpP[i][j] = can 's[i]' be black if you only consider the first 'j' segments
		ans it is the end of the 'j'th segment
	canP[i][j] = can the prefix i indexes be valid if you only consider the first 'j' segments
	
	dpS[i][j] = can 's[i]' be black if you only consider the last 'j, j+1... k' segments
		ans it is the start of the 'j'th segment
	canP[i][j] = can the idx 'i, i+1,...,n' be valid if you only consider the
		'j, j+1, ..., k' segments 

	to answer:
	check if idx 'i' can be black and/or white
*/

int n;
string s, ANS;
int cnt[MAXN];
int dpP[MAXN][MAXK], dpS[MAXN][MAXK], bl[MAXN], wh[MAXN];
bool canP[MAXN][MAXK], canS[MAXN][MAXK];
vector <int> c; int k;

string solve_puzzle(string S, vector<int> C) {
	s = '_'+S+'_'; n = s.size()-2;
	for(int i=1; i<=n; i++) cnt[i] = cnt[i-1] + (s[i]=='_');

	c.pb(-1);
	for(auto in : C) c.pb(in);
	k = c.size()-1;

	dpP[0][0] = 1; canP[0][0] = 1;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=k; j++){
			int len = c[j];
			// we want to put the segment on [i-c[j]+1, ..., i]
			if(i-c[j]+1 <= 0) continue;
			if(cnt[i]-cnt[i-c[j]] != 0) continue; // there is white
			if(s[i-c[j]] == 'X') continue; // can't make the segment 

			if(i-c[j]==0){ // extreme case
				if(canP[i-c[j]][j-1])
					dpP[i][j] = 1;

			} else if(canP[i-c[j]-1][j-1]){ // if j-1 segment is valid
				dpP[i][j] = 1; 
			}
		}

		// build canP
		for(int j=0; j<=k; j++){ // a[i] becomes ending of segment j
			if(s[i] != 'X'){ // use last canP and this dpP
				canP[i][j] = canP[i-1][j] | dpP[i][j];
			} else { // has to be X, so check dpP
				canP[i][j] = dpP[i][j];
			}
		}
	}
	dpS[n+1][k+1] = 1; canS[n+1][k+1] = 1;
	for(int i=n; i>=1; i--){
		for(int j=k; j>=1; j--){ // a[i] becomes start of segment j
			int len = c[j];
			// we want to put segment on [i, ..., i+c[j]-1]
			if(i+c[j]-1 > n) continue;
			if(cnt[i+c[j]-1]-cnt[i-1] != 0) continue;
			if(s[i+c[j]] == 'X') continue; // can't
			
			if(i+c[j]==n+1){ // extreme case
				if(canS[i+c[j]][j+1]) 
					dpS[i][j] = 1; 

			} else if(canS[i+c[j]+1][j+1]){
				dpS[i][j] = 1; 
			}
		}

		// build canS
		for(int j=k+1; j>=1; j--){
			if(s[i] != 'X'){
				canS[i][j] = canS[i+1][j] | dpS[i][j];
			} else {
				canS[i][j] = dpS[i][j];
			}
		}
	}

	for(int i=1; i<=n-1; i++){
		for(int j=1; j<=k; j++){
			if(dpP[i][j] && canS[i+2][j+1] && s[i+1] != 'X'){
				// if the prefix [1, ..., i] and suffix [i+2, ... , n] is valid
				bl[i-c[j]+1]++; bl[i+1]--;
				// prefix difference to update quickly
			}
		}
	}
	{
		int i=n; // extreme case
		if(dpP[i][k]){
			bl[i-c[k]+1]++; bl[i+1]--;
		}
	}

	for(int i=1; i<=n; i++){
		for(int j=0; j<=k; j++){
			if(canP[i-1][j] && canS[i+1][j+1]){
				// if [1, ..., i-1] and [i+1, ..., n] can put all segments
				wh[i] = 1;
			}
		}
	}

	for(int i=1; i<=n; i++) bl[i] += bl[i-1]; // prefix difference
	for(int i=1; i<=n; i++){
		if(s[i] != '.'){
			ANS += s[i]; continue;
		}
		if(bl[i] && wh[i]) ANS += '?';
		else if(bl[i]) ANS += 'X';
		else if(wh[i]) ANS += '_';
		else assert(false);
	}
	return ANS;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:45:8: warning: unused variable 'len' [-Wunused-variable]
   45 |    int len = c[j];
      |        ^~~
paint.cpp:72:8: warning: unused variable 'len' [-Wunused-variable]
   72 |    int len = c[j];
      |        ^~~

• 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