Submission #827997

#	Time	Username	Problem	Language	Result	Execution time	Memory
827997		Trunkty	Paint By Numbers (IOI16_paint)	C++14	80 / 100	3 ms	1620 KiB

paint

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll

#include "paint.h"

int n,k;
vector<int> c;
char arr[200005],ans[200005];
bool dp[205][205];

bool check(){
    for(int i=1;i<=n+2;i++){
        for(int j=0;j<=k;j++){
            dp[i][j] = false;
        }
    }
    dp[1][0] = true;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k-1;j++){
            if(dp[i][j]){
                if(arr[i]!='X'){
                    dp[i+1][j] = true;
                }
                if(arr[i+c[j]]=='X'){
                    continue;
                }
                bool yes = true;
                for(int l=i;l<i+c[j];l++){
                    if(arr[l]=='_'){
                        yes = false;
                    }
                }
                if(yes){
                    dp[i+c[j]+1LL][j+1] = true;
                }
            }
        }
        if(dp[i][k] and arr[i]!='X'){
            dp[i+1][k] = true;
        }
    }
    return (dp[n+1][k]||dp[n+2][k]);
}

string solve_puzzle(string S, vector<int> C){
    n = S.length();
    k = C.size();
    for(int i=1;i<=n;i++){
        arr[i] = S[i-1];
        ans[i] = S[i-1];
    }
    c = C;
    for(int i=1;i<=n;i++){
        if(ans[i]=='.'){
            bool x=false,o=false;
            arr[i] = 'X';
            if(check()){
                x = true;
            }
            arr[i] = '_';
            if(check()){
                o = true;
            }
            arr[i] = '.';
            if(x and o){
                ans[i] = '?';
            }
            else if(x){
                ans[i] = 'X';
            }
            else if(o){
                ans[i] = '_';
            }
            else{
                ans[i] = 'W';
            }
        }
    }
    string ret="";
    for(int i=1;i<=n;i++){
        ret += ans[i];
    }
    return ret;
}

• 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