Submission #585435

#	Time	Username	Problem	Language	Result	Execution time	Memory
585435		IvanJ	Paint By Numbers (IOI16_paint)	C++17	100 / 100	666 ms	185556 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;

const int maxn = 2e5 + 5;

int n, k;
int dp[maxn][105][2];
int cnt[maxn];
ll ans0[maxn], ans1[maxn];
vector<int> C;
string S;

int query(int x, int y) {
	int ret = cnt[y];
	if(x) ret -= cnt[x - 1];
	return ret;	
}

int rek(int pos, int x, int v) {
	if(dp[pos][x][v] != -1)
		return dp[pos][x][v];
	if(pos == n) return (x == k);
	int ret = 0;
	if(v == 0) {
		if(S[pos] != 'X') 
			ret = rek(pos + 1, x, 0) | rek(pos + 1, x, 1);
		if(ret) ans0[pos]++, ans0[pos + 1]--;
	} else {
		if (x < k && pos + C[x] <= n && query(pos, pos + C[x] - 1) == 0)
			ret = rek(pos + C[x], x + 1, 0);
		if(ret) ans1[pos]++, ans1[pos + C[x]]--;
	}
	return dp[pos][x][v] = ret;
}

string solve_puzzle(string s, vector<int> c) {
	n = s.size(), k = c.size();
	C = c, S = s;
    cnt[0] = (s[0] == '_');
    for(int i = 1;i < n;i++)
		cnt[i] = cnt[i - 1] + (s[i] == '_');
	
	memset(dp, -1, sizeof dp);
	rek(0, 0, 0);
	rek(0, 0, 1);
	for(int i = 1;i < n;i++) 
		ans0[i] += ans0[i - 1], ans1[i] += ans1[i - 1];
	
	string ret = "";
	for(int i = 0;i < n;i++) {
		if(s[i] != '.') ret += s[i]; 
		else if(ans0[i] && ans1[i]) ret += "?";
		else if(ans0[i]) ret += "_";
		else if(ans1[i]) ret += "X";	
		else assert(1 != 1);
	}
	return ret;
}

/*
int main() {
	string s;
	int K;
	vector<int> v;
	cin >> s >> K;
	for(int i = 0;i < K;i++) {
		int x;
		cin >> x;
		v.pb(x);
	}
	cout << solve_puzzle(s, v) << "\n";
	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