제출 #123830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
123830		khulegub	Paint By Numbers (IOI16_paint)	C++14	7 / 100	2 ms	504 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
//dont forgot to change the sizes of arrays

int pre[200020],suf[200020];
int dp[2][200][200020]; //dp 0 i j means -> 0-i clue in 0-j chars both inclusive, dp 1 i j means -> i-(k-1) clue in j-(n-1) chars both inclusive too
int last[200020];
bool wewe[200020], bebe[200020];
int bobo[200020];
int newdp[2][200][200020];
string solve_puzzle(string s, vector<int> c) {
	int n = s.length(), k = c.size();
	//suf & pre
	for (int i = 0; i < n; i++){
		if (i == 0){
			pre[i] = (int)(s[i] == '_');
			suf[n - 1 - i] = (int)(s[n - 1 - i] == '_');
		}
		else{
			pre[i] = (int)(s[i] == '_') + pre[i - 1];
			suf[n - 1 - i] = (int)(s[n - 1 - i] == '_') + suf[n - i];
		}
	}
	for (int i = 0; i < k; i++){ // first
		if (i == 0){
			for (int j = 0; j + c[i] - 1 < n; j++){
				if (pre[j + c[i] - 1] - pre[j] - (s[j] == '_') == 0){ // no underlines in da wei :3
					dp[0][i][j] = 1;
				}
			}
			for (int j = 0; j < n; j++){
				if(j == 0) last[j] = dp[0][i][j];
				else last[j] = last[j - 1] + dp[0][i][j];
			}
		}
		else{
			for (int j = c[i - 1] + 1; j + c[i] - 1 < n; j++){
				if (last[j - c[i - 1] - 1] > 0){
					if (pre[j + c[i] - 1] - pre[j] - (s[j] == '_') == 0){ //no underlinez in da wei :3
						dp[0][i][j] = 1;
					}
				}
			}
			for (int j = 0; j < n; j++){
				if(j == 0) last[j] = dp[0][i][j];
				else last[j] = last[j - 1] + dp[0][i][j];
			}
		}
	}
	for (int i = k - 1; i >= 0; i--){ //from last
		if (i == k - 1){
			for (int j = n - 1; j - c[i] + 1 >= 0; j--){
				if (suf[j - c[i] + 1] - suf[j] + (s[j] == '_') == 0){ //just like the past, no underlinez
					dp[1][i][j] = 1;
				}
			}
			for (int j = n - 1; j >= 0; j--){
				if (j == n - 1) last[j] = dp[1][i][j];
				else last[j] = last[j + 1] + dp[1][i][j];
			}
		}
		else{
			for (int j = n - 1 - c[i + 1] - 1; j - c[i] + 1 >= 0; j--){
				if (last[j + c[i + 1] + 1] > 0){
					if (suf[j - c[i] + 1] - suf[j] + (s[j] == '_') == 0){ //just like the past, no underlinez
						dp[1][i][j] = 1;
					}
				}
			}
			for (int j = n - 1; j >= 0; j--){
				if (j == n - 1) last[j] = dp[1][i][j];
				else last[j] = last[j + 1] + dp[1][i][j];
			}
		}
	}
	//preprocess again
	for(int i = 0; i < k; i++){
		for(int j = 0; j < n; j++){
			if (j == 0) newdp[0][i][j] = dp[0][i][j];
			else newdp[0][i][j] = dp[0][i][j] + newdp[0][i][j - 1];
		}
	}
	for(int i = k - 1; i >= 0; i--){
		for(int j = n - 1; j >= 0; j--){
			if (j == n - 1) newdp[1][i][j] = dp[1][i][j];
			else newdp[1][i][j] = dp[1][i][j] + newdp[1][i][j + 1];
		}
	}
	for(int j = 0; j < n; j++){
		//check if it can be white
		if(s[j] == 'X') continue;
		if(s[j] == '_') continue;
		bool can = 0;
		if((j + c[0] < n )){ // buh cluegee hoid tald ni tavich uzeh 
			if (newdp[1][0][j + c[0]] > 0) can = 1;
		}
		else if((j - c[k - 1] >= 0)){ //urd tald ni
			if (newdp[0][k - 1][j - c[k - 1]] > 0) can = 1;
		}
		for(int i = 0; i < k - 1; i++){ //0~(j-1), 0~i && (j+1)~(n-1), (i+1)~(k-1)
			if(can) break;
			if(j - c[i] < 0) continue;
			if(j + c[i + 1] >= n) continue;
			if (newdp[0][i][j - c[i]] > 0){
				if (newdp[1][i + 1][j + c[i + 1]] > 0){
					can = 1;
					break;
				}
			}
		}
		wewe[j] = can;
	}
	for (int i = 0; i < k; i++){
		for (int j = 0; j + c[i] - 1 < n; j++){
			if (pre[j + c[i] - 1] - pre[j] - (s[j] == '_') == 0){
				if (j + c[i] != n){
					if (s[j + c[i]] == 'X') continue;
				}
				if (j != 0){
					if (s[j - 1] == 'X') continue;
				}
				if (i != 0){
					if (j - 1 - c[i - 1] < 0) continue;
					if (newdp[0][i - 1][j - 1 - c[i - 1]] == 0) continue;
				}
				if (i != k - 1){
					if (j + c[i] + c[i + 1] >= n) continue;
					if (newdp[1][i + 1][j + c[i] + c[i + 1]] == 0) continue;
				}
				// cout << j << ' ' << c[i] << '\n';
				bobo[j] = max(bobo[j], c[i]);
			}
		}
	}
	for (int j = 0; j < n; j++){
		if (bobo[j] > 0){
			for (int l = j; l <= j + bobo[j] - 1; l++){
				bebe[l] = 1;
			}
		}
	}
	// for (int i = 0; i < k; i++){
	// 	for (int j = 0; j + c[i] - 1 < n; j++){ //can use prefix sum here to speed up
	// 		if(newdp[i][j] == 0) break;
	// 		if (dp[i][j] && (newdp[i][j] > 0)){
	// 			for (int l = j; l <= j + c[i] - 1; l++){
	// 				bebe[l] = 1;
	// 			}
	// 		}
	// 	}
	// }
	// for (int j = 0; j < n; j++){
	// 	cout << j << ' ';
	// }
	// cout << '\n';
	// for (int j = 0; j < n; j++){
	// 	cout << bebe[j];
	// 	if(j < 9) cout << ' ';
	// 	else cout << "  ";
	// }
	for (int j = 0; j < n; j++){
		if(s[j] == 'X') continue;
		if(s[j] == '_') continue;
		if(wewe[j] && bebe[j]) s[j] = '?';
		else if(wewe[j]) s[j] = '_';
		else s[j] = 'X';
	}



	// cout << s;

	// debugging
	// for (int j = 0; j < n; j++){
	// 	cout << j << ' ';
	// }
	// cout << '\n';
	// for (int j = 0; j < n; j++){
	// 	cout << wewe[j] << ((j<9)?" ":"  ");
	// }
	// cout << "\n#######\n";
	// for (int i = 0; i < k; i++){
	// 	for (int j = 0; j < n; j++){
	// 		cout << newdp[0][i][j] << ((j<9)?" ":"  ");
	// 	}
	// 	cout << '\n';
	// }
	return s;
}
// int main(){
// 	solve_puzzle(".......", {3, 3});
// }
//dont forgot to change the sizes of arrays

• 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