Submission #301347

#	Time	Username	Problem	Language	Result	Execution time	Memory
301347		williamMBDK	Paint By Numbers (IOI16_paint)	C++17	32 / 100	68 ms	88184 KiB

paint

#include<bits/stdc++.h>
#include "paint.h"
#include <cstdlib>
using namespace std;
const int MN = 200000;
int N, K;
string S;
vector<int> C;
vector<vector<int>> dp (MN + 10, vector<int> (101, -1));
vector<bool> x (MN), w(MN);
vector<int> pref (MN), pref2(MN);
int rec(int i1, int i2){
	if(dp[i1][i2] != -1) return dp[i1][i2];
	if(i2 == K){
		dp[i1][i2] = 1;
		if(i1 >= N) return 1;
		int c = pref2[N-1] - (i1 == 0 ? 0 : pref[i1-1]);
		dp[i1][i2] = c == 0;
		if(dp[i1][i2]){
			for(int i = i1; i < N; i++){
				if(w[i]) break;
				w[i] = 1;
			}
		}
		return dp[i1][i2];
	}
	dp[i1][i2] = 0;
	for(int i = i1; i + C[i2] - 1 < N; i++){
		int c = pref[i + C[i2] - 1] - (i == 0 ? 0 : pref[i-1]);
		bool b = c == 0;
		int t = i + C[i2];
		if(b && (t == N || S[t] != 'X') && rec(i + C[i2] + 1, i2+1)){
			if(t < N){
				w[t] = 1;
			}
			for(int j = i; j < i + C[i2]; j++){
				x[j] = 1;
			}
			for(int j = i1; j < i; j++){
				w[j] = 1;
			}
			for(int j = i1; j <= i; j++){
				dp[j][i2] = 1;
			}
		}
		if(S[i] == 'X') break;
	}
	//cout << i1 << " " << i2 << " " << dp[i1][i2] << endl;
	return dp[i1][i2];
}
string solve_puzzle(string _s, vector<int> _c) {
	//cout << "input: " << _s << endl;
	S = _s;
	C = _c;
	//for(auto e : C) cout << e << " ";
	//cout << endl;
	N = S.length();
	K = C.size();
	pref[0] = (S[0] == '_');
	for(int i = 1; i < N; i++){
		pref[i] = pref[i-1] + (S[i] == '_');
	}
	pref2[0] = (S[0] == 'X');
	for(int i = 1; i < N; i++){
		pref2[i] = pref[i-1] + (S[i] == 'X');
	}
	rec(0, 0);
	string res (N, '?');
	for(int i = 0; i < N; i++){
		if(S[i] == 'X') x[i] = 1;
		else if(S[i] == '_') w[i] = 1;
		if(w[i] == 0 && x[i] == 0) w[i] = 1;
		if(x[i] && !w[i]) res[i] = 'X';
		else if(!x[i] && w[i]) res[i] = '_';
	}
	return res;
}

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