Submission #642571

#	Time	Username	Problem	Language	Result	Execution time	Memory
642571		ymm	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	368 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200010;
const int K = 110;
int next_[N];
bool isx[N];
bool dp1[N][K], dp2[N][K];
int canx[N];
int can_[N];
int n, k;

std::string solve_puzzle(std::string s, std::vector<int> c) {
	n = s.size();
	k = c.size();
	next_[n] = N;
	LoopR (i,0,n) {
		next_[i] = s[i] == '_'? i: next_[i+1];
		isx[i] = s[i] == 'x' || s[i] == 'X';
	}
	dp1[0][0] = 1;
	Loop (i,1,n+1) {
		dp1[i][0] = s[i-1] != 'X' && dp1[i-1][0];
		Loop (j,0,k) {
			dp1[i][j+1] |= i >= c[j] && ((i-c[j]==0&&j==0) || dp1[i-c[j]-1][j]) && !isx[i] && next_[i-c[j]] >= i;
			dp1[i][j+1] |= !isx[i-1] && dp1[i-1][j+1];
		}
	}
	dp2[n][k] = 1;
	LoopR (i,0,n) {
		dp2[i][k] = s[i] != 'X' && dp2[i+1][k];
		Loop (j,0,k) {
			dp2[i][j] |= i+c[j] <= n && ((i+c[j]==n&&j+1==k) || dp2[i+c[j]+1][j+1]) && !isx[i+c[j]] && next_[i] >= i+c[j];
			dp2[i][j] |= !isx[i] && dp2[i+1][j];
		}
	}
	Loop (i,0,n)
		Loop (j,0,k+1)
			can_[i] |= dp1[i][j] && dp2[i+1][j] && !isx[i];
	Loop (j,0,k) {
		Loop (i,0,n-c[j]+1) {
			int tmp =    ((i==0&&j==0) || dp1[i-1][j])
			          && ((i+c[j]==n&&j==k-1) || dp2[i+c[j]+1][j+1])
				  && next_[i] >= i+c[j]
				  && !isx[i+c[j]] && (i==0||!isx[i-1]);
			canx[i     ] += tmp;
			canx[i+c[j]] -= tmp;
		}
	}
	Loop (i,0,n)
		canx[i+1] += canx[i];
	string ans(n, '.');
	Loop (i,0,n) {
		     if (canx[i] && can_[i]) s[i] = '?';
		else if (canx[i]           ) s[i] = 'X';
		else if (           can_[i]) s[i] = '_';
		else                         assert(false);
	}
	return s;
}	

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10