Submission #311245

#	Time	Username	Problem	Language	Result	Execution time	Memory
311245		tengiz05	Paint By Numbers (IOI16_paint)	C++17	0 / 100	1 ms	384 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];
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;
		}
	}
	// calc suffix
	for(int i=n;i>=0;i--)sum[i] = ((i==n)?0 : sum[i+1]+(int)(s[i]=='_'));
//	for(int i=0;i<=n;i++)cout << sum[i];cout<<'\n';
	
	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;
		}
	}
	/*cout << '\n';
	for(int j=0;j<k;j++){
		for(int i=0;i<=n;i++)
			cout << suff[i][j];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];
		}
	}
	string ans(n, '?');
	for(int i=0;i<n;i++){
		if(s[i] != '.'){
			ans[i] = s[i]; 
			continue;
		}
		bool X = false;
		bool _ = false;
		int cnt = 0;
		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 && ((i==0)?true:prefor[i-1][j-1]^1))
			|| ((int)((j==0)?1:((i-2<0)?0:prefor[i-2][j-1])) + ((j==k)?1:((i+2>n)?0:suffor[i][j])) > 1 && ((i==n-1)?true:suffor[i+1][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;
				cnt++;
			}
		}
		if(X && !_)ans[i] = 'X';
		if(_ && !X)ans[i] = '_';
	}
	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