Submission #728179

#	Time	Username	Problem	Language	Result	Execution time	Memory
728179		penguin133	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	372 KiB

paint

#include <bits/stdc++.h>
using namespace std;
#include "paint.h"
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int P[5005][105], S[5005][105];

std::string solve_puzzle(std::string s, std::vector<int> c) {
	int n = (int)s.length(), k = (int)c.size();
	string ans;
	P[0][0] = 1;
	S[n+1][k+1] = 1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++){
			if(s[i-1] != 'X')P[i][j] |= P[i-1][j];
			bool f = 1;
			if(!j || c[j-1] > i - 1)continue;
			for(int a=i-1;a>=i-c[j-1];a--)if(s[a-1] == '_')f = 0;
			if(s[i-1] == 'X')f = 0;
			if(f){
				P[i][j] |= P[i - c[j-1] - 1][j - 1];
			}
		}
	}
	for(int i=n;i>=1;i--){
		for(int j=k+1;j>=1;j--){
			if(s[i-1] != 'X')S[i][j] |= S[i+1][j];
			bool f = 1;
			if(!j || i + c[j-1] > n)continue;
			for(int a=i+1;a<=i+c[j-1];a++)if(s[a-1] == '_')f = 0;
			if(s[i-1] == 'X')f = 0;
			if(f){
				S[i][j] |= S[i + c[j-1] + 1][j + 1];
			}
		}
	}
	//cerr << "brozo";
	for(int i=1;i<=n;i++){
		if(s[i-1] == 'X' || s[i-1] == '_'){
			ans += s[i-1];
			continue;
		}
		bool f = 0;
		for(int j=0;j<=k;j++)if(P[i][j] && S[i][j+1])f = 1;
		bool brub = 0;
		for(int j=1;j<=k;j++){
			int in = max(1, i - c[j-1] + 1), in2 = in;
			int sm = 0;
			for(int a= max(1, i-c[j-1] + 1); a <= min(i, n - c[j-1] + 1); a++){
				bool f2 = 1;
				while(in <= a+c[j-1]+1){
					if(s[in-1] == '_')sm++;
					in++;
				}
				while(in2 < a){
					if(s[in2-1] == '_')sm--;
					in2++;
				}
				if(sm)f2 =0 ;
				//for(int b=a;b<=a+c[j-1]-1;b++)if(s[b-1] == '_')f2 = 0;
				if(a > 1 && s[a-2] == 'X')f2 = 0;
				if(a + c[j-1] - 1 < n && s[a + c[j-1] - 1] == 'X')f2 = 0;
				if(!f2)continue;
				if(P[a-1][j-1] && S[a + c[j-1]][j+1]){
					//cout << i << ' ' << j << ' ' << a << '\n';
					brub = 1;
				}
			}
		}
		if(brub && f)ans += "?";
		else if(f)ans += "_";
		else ans += "X";
	}
	return ans;
}

• 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