Submission #935070

#	Time	Username	Problem	Language	Result	Execution time	Memory
935070		oblantis	Paint By Numbers (IOI16_paint)	C++17	100 / 100	200 ms	80652 KiB

paint

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 2e5 + 4;
//#include "paint.h"
bool dp[maxn][101], pd[maxn][101], DP[maxn][101], PD[maxn][101];
string solve_puzzle(string s, vector<int> c) {
	int n = s.size(), k = c.size();
	dp[0][0] = DP[0][0] = 1;
	s = "$" + s + "$";
	for(int i = 1, ls = 0; i <= n; i++){
		if(s[i] == '_'){
			ls = i;
			for(int j = 0; j <= k; j++)DP[i][j] = DP[i - 1][j];
		}
		else {
			for(int j = 0; j < k; j++){
				if(ls <= i - c[j]){
					if(i == c[j]){
						if(j == 0)dp[i][1] = 1;
					}
					else if(s[i - c[j]] != 'X')dp[i][j + 1] |= DP[i - c[j] - 1][j];
				}
			}
			if(s[i] == 'X'){
				for(int j = 0; j <= k; j++)DP[i][j] = dp[i][j];
			}
			else for(int j = 0; j <= k; j++)DP[i][j] = dp[i][j] | DP[i - 1][j];
		}
	}
	pd[n + 1][0] = PD[n + 1][0] = 1;
	for(int i = n, ls = n + 1; i >= 1; i--){
		if(s[i] == '_'){
			ls = i;
			for(int j = 0; j <= k; j++)PD[i][j] = PD[i + 1][j];
		}
		else {
			for(int j = 0; j < k; j++){
				if(ls >= i + c[k - j - 1]){
					if(i + c[k - j - 1] == n + 1){
						if(j == 0)pd[i][1] = 1;
					}
					else if(s[i + c[k - j - 1]] != 'X')pd[i][j + 1] |= PD[i + c[k - j - 1] + 1][j];
				}
			}
			if(s[i] == 'X'){
				for(int j = 0; j <= k; j++)PD[i][j] = pd[i][j];
			}
			else for(int j = 0; j <= k; j++)PD[i][j] = pd[i][j] | PD[i + 1][j];
		}
	}
	string ret = "";
	int r = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < k; j++){
			if(s[i - 1] != 'X' && ((i == 1) ? (j == 0) : DP[i - 2][j]) && pd[i][k - j])r = max(r, i + c[j] - 1);
		}
		if(s[i] != '.'){
			ret += s[i];
			continue;
		}
		if(i <= r){
			bool ok = 0;
			for(int j = 0; j <= k; j++){
				if(s[i] != 'X' && DP[i - 1][j] && PD[i + 1][k - j]){
					ok = 1;
					break;
				}
			}
			if(ok)ret += '?';
			else ret += 'X';
		}
		else ret += '_';
	}
	return ret;
}

//void solve() {
	//string s;
	//int n;
	//cin >> s >> n;
	//vt<int> c(n);
	//for(int i = 0; i < n; i++){
		//cin >> c[i];
	//}
	//cout << solve_puzzle(s, c);
//}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//int times = 1;
	////cin >> times;
	//for(int i = 1; i <= times; i++) {
		//solve();
	//}
	//return 0;
//}

• 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