Submission #312824

#	Time	Username	Problem	Language	Result	Execution time	Memory
312824		tengiz05	Paint By Numbers (IOI16_paint)	C++17	32 / 100	7 ms	1184 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];
bool prefor[N][105], suffor[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(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;
		}
	}/*
	for(int j=0;j<k;j++){
		for(int i=0;i<=n;i++)cout << pref[i][j];cout << '\n';
	}cout << "\n";*/
	// 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(s[i] == '_' || i+c[j]-1>=n)continue;
			if(sum[i] == ((i+c[j] > n)? 0: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 j=0;j<k;j++){
		for(int i=0;i<=n;i++)cout << suff[i][j];cout << '\n';
	}cout << "\n";*/
	for(int j=0;j<k;j++){
		for(int i=0;i<=n;i++){
			prefor[i][j] = pref[i][j];
			if(i>0)prefor[i][j] |= prefor[i-1][j];
		}
	}
	for(int j=0;j<k;j++){
		for(int i=n;i>=0;i--){
			suffor[i][j] = suff[i][j];
			if(i<n)suffor[i][j] |= suffor[i+1][j];
		}
	}
	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:prefor[i-2][j-1])) + ((j+1>=k)?1:((i+c[j]+1>=n)?0:suffor[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:prefor[i][j-1]) + ((j==k)?1:((i+2>n)?0:suffor[i+2][j])) > 1))
			 || (int)((j==0)?1:((i-2<0)?0:prefor[i-2][j-1])) + ((j==k)?1:(suffor[i][j])) > 1)){
				X = true;
			}*/
			if((int)((j==0)?1:((i==0)?0:prefor[i-1][j-1])) + ((j==k)?1:suffor[i+1][j]) > 1){
				_ = true;
			}
		}
	//	cout << X << ' ' << _ << '\n';
		if(X && !_)ans[i] = 'X';
		if(_ && !X)ans[i] = '_';
	}
	return ans;
}
/*

....._.._.
2 3 2

._._
2 1 1

.
1 1

*/

• 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