Submission #795676

#	Time	Username	Problem	Language	Result	Execution time	Memory
795676		allin27x	Paint By Numbers (IOI16_paint)	C++17	100 / 100	402 ms	63456 KiB

paint

#include <bits/stdc++.h>
using namespace std;

bool dpl[103][(int)2e5+7];
bool dpr[103][(int)2e5+7];
bool can[103][(int)2e5+7];
int pr_w[(int)2e5+7];
int pr_b[(int)2e5+7];

int cnt_w(int l, int r) {return pr_w[r+1]-pr_w[l];}
int cnt_b(int l, int r) {return pr_b[r+1]-pr_b[l];}

string solve_puzzle(string s, vector<int> c){
	int n = s.size(); int k = c.size();
	for (int i=0; i<n; i++) pr_w[i+1] = pr_w[i] + (s[i] == '_');
	for (int i=0; i<n; i++) pr_b[i+1] = pr_b[i] + (s[i] == 'X');
	for (int i=0; i<n; i++) dpl[0][i] = !cnt_b(0, i);
	for (int i=n-1; i>=0; i--) dpr[0][i] = !cnt_b(i, n-1);

	for (int i=1; i<=k; i++){
		for (int x=0; x<n; x++){
			if (x + 1 < c[i-1]) continue;
			if (x+1 == c[i-1]) {dpl[i][x] = (i==1)?!cnt_w(0,x): 0; continue;}
			bool c1 = dpl[i][x-1];
			bool c2 = (s[x-c[i-1]] != 'X') && !cnt_w(x-c[i-1]+1, x);
			if (x!=c[i-1]) c2=c2&& dpl[i-1][x-c[i-1]-1]; else c2=c2&&(i==1);
			if (s[x] == '_') {dpl[i][x] = c1; continue;}
			if (s[x] == 'X') {dpl[i][x] = c2; continue;}
			dpl[i][x] = c1 || c2;
		}	
	}

	for (int i=1; i<=k; i++){
		for (int x=n-1; x>=0; x--){
			if (n-x < c[k-i]) continue;
			if (n-x == c[k-i]) {dpr[i][x] = (i==1)?!cnt_w(x, n-1): 0; continue;}
			bool c1 = dpr[i][x+1];
			bool c2 = (s[x+c[k-i]] != 'X') && !cnt_w(x, x+c[k-i]-1);
			if (n-x-1!=c[k-i]) c2=c2&& dpr[i-1][x+c[k-i]+1]; else c2=c2&&(i==1);
			if (s[x] == '_') {dpr[i][x] = c1; continue;}
			if (s[x] == 'X') {dpr[i][x] = c2; continue;}
			dpr[i][x] = c1 || c2;
		}	
	}
	vector<int> black(n,0);
	vector<int> white(n,0);
	for (int i=0; i<k; i++){
		int sum = 0;
		for (int x=0; x<n; x++){
			bool cr; if (x+c[i]==n) cr = 1; else cr = s[x+c[i]] != 'X';
			bool cl; if (x==0) cl = 1; else cl = s[x-1] != 'X';
			bool cm = !cnt_w(x, x+c[i]-1);
			bool pl; if (x<2) pl = (i==0); else pl = dpl[i][x-2];
			bool pr; if (x+c[i]>=n-1) pr = (i==k-1); else pr=dpr[k-i-1][x+c[i]+1];
			can[i][x] = cr&&cl&&cm&&pl&&pr;
			sum += can[i][x];
			if (x>=c[i]) sum-=can[i][x-c[i]];
			black[x] = black[x] || sum;
		}
	}

	for (int x=0; x<n; x++){
		if (s[x] == 'X') continue;
		for (int i=0; i<=k; i++){
			bool cl; if (x==0) cl=(i==0); else cl = dpl[i][x-1];
			bool cr; if (x==n-1) cr=(i==k); else cr = dpr[k-i][x+1];
			white[x] = white[x] || (cl&&cr);
		}
	}
	string res(n, '?');
	for (int i=0; i<n; i++) if (!white[i]) res[i] = 'X';
			else if (!black[i]) res[i] = '_';
	return res;
}

• 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