제출 #998612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
998612		hasan2006	Paint By Numbers (IOI16_paint)	C++17	100 / 100	236 ms	49500 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;

#define all(s) s.begin(),s.end()
#define pb push_back
#define ll long long

const int N = 2e5 + 17,  K = 100 + 17;
int a[N], b1[N], b2[N];
bool dp1[N][K], dp2[N][K];

string solve_puzzle(string s, vector<int> c) {
	int i , j , n = s.size() , k = c.size();
	for(int i = 0; i < n; i++)
		a[i + 1] = a[i] + (s[i] == '_');
	dp1[0][0] = dp2[n][k] = 1;
	for(i = 0; i < n; i++){
		for(j = 0; j <= k; j++){
			if(s[i] != 'X')
				dp1[i + 1][j] |= dp1[i][j];
			if(j < k && i + c[j] < n && s[i + c[j]]^'X')
                if(a[i + c[j]] == a[i])
                    dp1[i+c[j]+1][j+1] |= dp1[i][j];
		}
	}
	for(int i = n; i > 0; i--) {
		for(int j = 0; j <= k; j++) {
			if(s[i - 1] != 'X')
				dp2[i - 1][j] |= dp2[i][j];
			if(j && i - c[j - 1] > 0 && s[i - c[j - 1] - 1] ^ 'X')
                if(a[i] == a[i - c[j - 1]])
                    dp2[i - c[j - 1] - 1][j - 1] |= dp2[i][j];
		}
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j <= k; j++)
			b1[i] |= dp1[i + 1][j] && dp2[i][j];
		for(int j = 0; j < k; j++) {
			if(i + c[j] <= n && dp1[i][j] && dp2[i + c[j]][j + 1] && a[i + c[j]] == a[i]) {
				b2[i]++;
				b2[i + c[j]]--;
			}
		}
		b2[i + 1] += b2[i];
		if(b1[i] && b2[i])
            s[i] = '?';
        else if(b1[i])
            s[i] = '_';
        else
            s[i] = 'X';
	}
    return s;
}

• 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