제출 #312856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
312856		tengiz05	Paint By Numbers (IOI16_paint)	C++17	59 / 100	12 ms	1320 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n, k;
bool pref[N][105], suff[N][105];
int sum[N];
bool xx[N];
string solve_puzzle(string s, vector<int> c) {
	n = s.length();
	k = c.size();
	s += '_';
	//calc prefix
	for(int i=0;i<=n;i++)sum[i] = ((i==0)? 0 : sum[i-1])+(int)(s[i]=='_');
	for(int j=0;j<k;j++){
		for(int i=0;i<n;i++){
			if(i>0)pref[i][j] |= pref[i-1][j];
			if(s[i] == '_' || i-c[j]+1 < 0)continue;
			if(sum[i] == ((i-c[j] < 0)? 0:sum[i-c[j]]) && 
				(j==0 || (i-c[j]-1>=0&&pref[i-c[j]-1][j-1] == true)))pref[i][j] = true;
		}
	}
	// calc suffix
	for(int i=n;i>=0;i--)sum[i] = ((i==n)?0 : sum[i+1]+(int)(s[i]=='_'));
	for(int j=k-1;j>=0;j--){
		for(int i=n-1;i>=0;i--){
			if(i<n-1)suff[i][j]|=suff[i+1][j];
			if(s[i] == '_' || i+c[j]-1>=n)continue;
			if(sum[i] == (sum[i+c[j]]) &&
				(j==k-1 || (i+c[j]+1<=n&&suff[i+c[j]+1][j+1] == true)))suff[i][j] = true;
		}
	}
	for(int i=0;i<=n;i++)sum[i] = ((i==0)? 0 : sum[i-1])+(int)(s[i]=='_');
	for(int j=0;j<k;j++){
		vector<int> pr(N,0);
		for(int i=0;i<n;i++){
			if(k!=j&&(i+c[j] > n || ((i==0)?0:sum[i-1]) != sum[i+c[j]-1]))continue;
			if((int)((j==0)?1:((i-2<0)?0:pref[i-2][j-1])) + ((j+1>=k)?1:((i+c[j]+1>=n)?0:suff[i+c[j]+1][j+1])) > 1
			 && ((i==0)?1:s[i-1]!='X') && s[i+c[j]] != 'X'){pr[i]++, pr[i+c[j]]--;}
		}for(int i=0;i<n;i++){
			pr[i] = (i==0)?pr[i]:pr[i]+pr[i-1];
			if(pr[i])xx[i] = true;
		}
	}
	
	string ans(n, '?');
	for(int i=0;i<n;i++){
		if(s[i] != '.'){
			ans[i] = s[i]; 
			continue;
		}
		bool X = xx[i];
		bool _ = false;
		for(int j=0;j<=k;j++){
			if((int)((j==0)?1:((i==0)?0:pref[i-1][j-1])) + ((j==k)?1:suff[i+1][j]) > 1){
				_ = true;
			}
		}
	//	cout << X << ' ' << _ << '\n';
		if(X && !_)ans[i] = 'X';
		if(_ && !X)ans[i] = '_';
	}
	return ans;
}
/*

...........
2 1 9

._._
2 1 1

.
1 1

............__._..
2 10 1

*/

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