제출 #241680

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241680		crossing0ver	Paint By Numbers (IOI16_paint)	C++17	32 / 100	5 ms	512 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[i] == 0 && i == 1) continue;
		if (x[i] == 1 && i == 0) continue;
		if (i == 0) 
			dpL[pos][k][0] = dpL[pos-1][k][0]|dpL[pos-1][k][1];
		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) {
	for (int i = 0; i < 2; i++) {
		if (x[i] == 0 && i == 1) continue;
		if (x[i] == 1 && i == 0) continue;
		if (i == 0) {
			dpR[pos][k][0] = dpR[pos + 1][k][0]|dpR[pos+1][k][1];
		}		
		if (i == 1) {
			if (i + c[k] > R[0][i] || c[k] == 0) {
			dpR[pos][k][1] = 0;
			continue;
			}
			dpR[pos][k][1] = dpR[pos + c[k]][k+1][0];
		}                                   
	}
}


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] = 1;
	for (int i = 1;i <= n; i++) 
		for (int j = 0; j <= k-1; j++) 
			checkL(i,j);	
	//		cout << n <<'\n';
	for (int i  = n; i > 0; i--)
	for (int j = k-1; j >= 0; j--) {
		checkR(i,j);
	}
		
	for (int i = 1;i  <= n; i++) {
		for (int j = 0; j < k;j++) {
			if (dpL[i][j][0] == 1 && (dpR[i][j+1][0] == 1) )
				white[i] = 1;
			for (int e = i; e < i + c[j]; e++)
			black[i]|= (dpL[e][j][1] & dpR[e+1][j+1][0]);
		}
	}
	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
*/

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10