Submission #728194

#	Time	Username	Problem	Language	Result	Execution time	Memory
728194		penguin133	Paint By Numbers (IOI16_paint)	C++17	100 / 100	635 ms	63128 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());

bool P[200005][105], S[200005][105], pos[200005][105];
int lst[105], ptr1[105], ptr2[105], cnt[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<=k;i++)ptr1[i] = ptr2[i] = 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;
			while(ptr1[j] <= i - 1){
				if(s[ptr1[j] - 1] == '_')cnt[j]++;
				ptr1[j]++;
			}
			while(ptr2[j] < i - c[j-1]){
				if(s[ptr2[j] - 1] == '_')cnt[j]--;
				ptr2[j]++;
			}
			//for(int a=i-1;a>=i-c[j-1];a--)if(s[a-1] == '_')f = 0;
			if(cnt[j])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=1;i<=k;i++)ptr1[i] = ptr2[i] = n, cnt[i] = 0;
	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 == k + 1 || i + c[j-1] > n)continue;
			while(ptr1[j] >= i + 1){
				if(s[ptr1[j] - 1] == '_')cnt[j]++;
				ptr1[j]--;
			}
			while(ptr2[j] > i + c[j-1]){
				if(s[ptr2[j] - 1] == '_')cnt[j]--;
				ptr2[j]--;
			}
			//for(int a=i+1;a<=i+c[j-1];a++)if(s[a-1] == '_')f = 0;
			if(cnt[j])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 j=1;j<=k;j++){
		int in = 1, in2 = in;
		int sm = 0;
		for(int a=1;a<=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';
				pos[a][j] = 1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){
			if(pos[i][j])lst[j] = 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 lb = max(1, i - c[j-1] + 1);
			if(lst[j] >= lb)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: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10