Submission #120303

#	Time	Username	Problem	Language	Result	Execution time	Memory
120303		turbat	Paint By Numbers (IOI16_paint)	C++14	90 / 100	483 ms	494720 KiB

paint

    #include "paint.h"
    #include <bits/stdc++.h>
    using namespace std;
    #define N 300005
     
    int n, k, cnt[N], can[N], dp[N][205], paint[N];
    vector <int> c;
    string s, ans;
     
    int solve(int idx, int col){
    	if (!col && !idx) return 1;
    	if (idx < 0) return 0;
    	if (dp[idx][col] != -1) return dp[idx][col];
    	dp[idx][col] = 0;
    	// cout << idx << ' '<< col << endl;
    	if (s[idx] != 'X' && solve(idx - 1, col)) can[idx] = dp[idx][col] = 1;
    	if (col && cnt[idx] - cnt[idx - c[col - 1]] == 0 && s[idx - c[col - 1]] != 'X')
    		if ((col == 1 && !(idx - c[col - 1])) || solve(idx - c[col - 1] - 1, col - 1)){
    			dp[idx][col] = 1;
    			paint[idx]++;
    			paint[idx - c[col - 1]]--;
    			can[idx - c[col - 1]] = 1;
    		}
    	// cout << idx << ' '<< col << ' '<< dp[idx][col]<< endl;
    	return dp[idx][col];
    }
    string solve_puzzle(string ss, vector<int> cc) {
    	s = '_' + ss;
    	c = cc;
    	n = s.size();
    	k = c.size();
    	for (int i = 1;i < n;i++){
    		if (s[i] == '_') cnt[i]++;
    		cnt[i] += cnt[i - 1];
    	}
    	memset(dp, -1, sizeof dp);
    	solve(n - 1, k);
    	for (int i = n - 1;i > 0;i--) paint[i] += paint[i + 1];
    	for (int i = 1;i < n;i++){
    		int d = 0;
    		if (paint[i]) d += 1;
    		if (can[i]) d += 2;
    		if (!d) ans += 'G';
    		if (d == 1) ans += 'X';
    		if (d == 2) ans += '_';
    		if (d == 3) ans += '?';
    	}
    	return ans;
    }

• 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: 0 / 10