제출 #290088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290088		shayan_p	Paint By Numbers (IOI16_paint)	C++17	80 / 100	9 ms	896 KiB

paint

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

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k)) & 1)
#define any STRANGE

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int maxn = 110, mod = 1e9 + 7, inf = 1e9 + 10;

bool dp[maxn][maxn], any[maxn][maxn];

bool solve(string &s, vector<int> &c){
    for(int i = 1; i <= sz(s); i++){
	any[i][i] = s[i-1] == '_';
	for(int j = i+1; j <= sz(s); j++){
	    any[i][j]= any[i][j-1] || s[j-1] == '_';
	}
    }
    dp[0][0] = 1;
    for(int i = 0; i <= sz(c); i++){
	for(int j = 1; j <= sz(s); j++){
	    dp[i][j] = 0;
	    if(s[j-1] != 'X')
		dp[i][j]|= dp[i][j-1];
	    if(i > 0){
		if(j > c[i-1])
		    dp[i][j]|= !any[j-c[i-1]+1][j] && s[j-1-c[i-1]] != 'X' && dp[i-1][j-c[i-1]-1];
		if(j == c[i-1])
		    dp[i][j]|= !any[1][j] && i == 1;
	    }
	}
    }
    return dp[sz(c)][sz(s)];
}
string solve_puzzle(string s, vector<int> c){
    string ans = s;
    for(int i = 0; i < sz(s); i++){
	if(s[i] == '.'){
	    s[i] = 'X';
	    bool A = solve(s, c);
	    s[i] = '_';
	    bool B = solve(s, c);
	    if(A && B)
		ans[i] = '?';
	    else if(A)
		ans[i] = 'X';
	    else if(B)
		ans[i] = '_';
	    else
		assert(0);
	    s[i] = '.';		
	}		    
    }
    return ans;
}

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