제출 #241670

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

• Subtask 1: 0 / 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