Submission #388828

#	Time	Username	Problem	Language	Result	Execution time	Memory
388828		Keshi	Paint By Numbers (IOI16_paint)	C++17	100 / 100	514 ms	168680 KiB

paint

//In the name of God
#include<bits/stdc++.h>
#include "paint.h"
#include <cstdlib>
using namespace std;

typedef int ll;
typedef pair<ll, ll> pll;

const ll maxn = 2e5 + 100;
const ll maxk = 105;

#define pb push_back
#define F first
#define S second
#define Mp make_pair
#define all(x) (x).begin(), (x).end()
#define Sz(x) ll((x).size())


ll n;

bitset<maxn> dp[maxk], pd[maxk], dp2[maxk];

ll psx[maxn], ps_[maxn], ps2[maxk][maxn << 1];
ll isx[maxn], is_[maxn];

bool canx(ll l, ll r){
	if(l < 1 || r > n + 1) return 0;
	return (ps_[r - 1] - ps_[l - 1] == 0);
}
bool can_(ll l, ll r){
	if(l < 1 || r > n + 1) return 1;
	return (psx[r - 1] - psx[l - 1] == 0);
}

string solve_puzzle(string s, vector<int> C){
	n = Sz(s);
	ll k = Sz(C);
	vector<ll> c;
	c.pb(-1);
	for(ll i : C){
		c.pb(i);
	}
	s = ' ' + s;
	dp[0][0] = 1;
	pd[0][n + 1] = 1;
	pd[0][n + 2] = 1;
	for(ll i = 1; i <= n; i++){
		isx[i] = ll(s[i] == 'X');
		is_[i] = ll(s[i] == '_');
		psx[i] = psx[i - 1] + isx[i];
		ps_[i] = ps_[i - 1] + is_[i];
	}
	for(ll i = 1; i <= n; i++){
		dp[0][i] = can_(1, i + 1);
		pd[0][i] = can_(i, n + 1);
	}
	for(ll i = 1; i <= k; i++){
		for(ll j = 1; j <= n; j++){
			dp[i][j] = (dp[i][j - 1] && can_(j, j + 1));
			bool ok = 0;
			if(j - c[i] - 1 >= 0) ok = dp[i - 1][j - c[i] - 1];
			else ok = (i == 1);
			if(canx(j - c[i] + 1, j + 1) && can_(j - c[i], j - c[i] + 1) && ok) dp[i][j] = 1;
		}
		for(ll j = n; j > 0; j--){
			pd[i][j] = (pd[i][j + 1] && can_(j, j + 1));
			if(canx(j, j + c[k - i + 1])&&can_(j + c[k - i + 1], j + c[k - i + 1] + 1) && pd[i - 1][j + c[k - i + 1] + 1]) pd[i][j] = 1;
		}
/*		for(ll j = 1; j <= n; j++){
			cout << dp[i][j];
		}
		cout << "\n";
		for(ll j = 1; j <= n; j++){
			cout << pd[i][j];
		}
		cout << "\n";*/
	}
	for(ll i = 1; i <= n; i++){
		if(isx[i]) continue;
		isx[i] = 1;
		for(ll j = 0; j <= k; j++){
			if(dp[j][i - 1] && pd[k - j][i + 1]) isx[i] = 0;
		}
	}
	for(ll i = 1; i <= k; i++){
		for(ll j = 1; j <= n; j++){
			bool ok = 0;
			if(j - c[i] - 1 >= 0) ok = dp[i - 1][j - c[i] - 1];
			else ok = (i == 1);
			dp2[i][j] = canx(j - c[i] + 1, j + 1) && can_(j - c[i], j - c[i] + 1) && can_(j + 1, j + 2) && ok && pd[k - i][j + 2];
			ps2[i][j] = ps2[i][j - 1] + dp2[i][j];
		}
		for(ll j = n + 1; j <= n + n; j++){
			ps2[i][j] = ps2[i][j - 1];
		}
	}
	for(ll i = 1; i <= n; i++){
		if(is_[i]) continue;
		is_[i] = 1;
		for(ll j = 1; j <= k; j++){
			if(ps2[j][i + c[j] - 1] != ps2[j][i - 1]) is_[i] = 0;
		}
	}
	string d;
	for(ll i = 1; i <= n; i++){
		if(is_[i]) d += '_';
		else if(isx[i]) d += 'X';
		else d += '?';
	}

    return d;
}

• 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