Submission #147257

#	Time	Username	Problem	Language	Result	Execution time	Memory
147257		alexandra_udristoiu	Paint By Numbers (IOI16_paint)	C++14	100 / 100	363 ms	82212 KiB

paint

#include "paint.h"
#include<cstdlib>
#include<iostream>
#include<vector>
#include<string>
#include<bitset>
#define DIM 200005
using namespace std;
static string sol;
static int sum[DIM], ff[DIM];
static short df[103][DIM], ds[103][DIM];
string solve_puzzle(string c, vector<int> v) {
    int n, k, i, j, ok;
    n = c.size();
    k = v.size();
    c += '0';
    v.push_back(0);
    for(i = n; i >= 1; i--){
        c[i] = c[i - 1];
    }
    for(i = k; i >= 1; i--){
        v[i] = v[i - 1];
    }
    for(i = 1; i <= n; i++){
        sum[i] = sum[i - 1];
        if(c[i] == '_'){
            sum[i]++;
        }
    }
    c[0] = '0';
    c += '0';
    df[0][0] = 1;
    for(i = 0; i <= k; i++){
        for(j = 1; j <= n; j++){
            if(c[j] != 'X' && df[i][j - 1] == 1){
                df[i][j] = 1;
            }
            if(j >= v[i] && sum[j] - sum[ j - v[i] ] == 0 && df[i - 1][ max(0, j - v[i] - 1) ] == 1 && c[j - v[i] ] != 'X'){
                df[i][j] = 1;
            }
        }
    }
    ds[k + 1][n + 1] = 1;
    v.push_back(0);
    for(i = k + 1; i >= 1; i--){
        for(j = n; j >= 1; j--){
            if(c[j] != 'X' && ds[i][j + 1] == 1){
                ds[i][j] = 1;
            }
            if(j + v[i] - 1 <= n && sum[j + v[i] - 1] - sum[j - 1] == 0 && ds[i + 1][ min(j + v[i] + 1, n + 1) ] == 1 && c[j + v[i] ] != 'X'){
                ds[i][j] = 1;
                if(df[i - 1][ max(0, j - 2) ] == 1 && c[j - 1] != 'X'){
                    ff[j]++;
                    ff[ j + v[i] ]--;
                }
            }
        }
    }
    for(i = 1; i <= n; i++){
        ff[i] += ff[i - 1];
        ok = 0;
        for(j = 0; j <= k; j++){
            if(df[j][i - 1] == 1 && ds[j + 1][i + 1] == 1){
                ok = 1;
            }
        }
        if(c[i] == 'X'){
            ok = 0;
        }
        if(ok == 1 && ff[i] > 0){
            sol += '?';
        }
        else{
            if(ok == 1){
                sol += '_';
            }
            else{
                sol += 'X';
            }
        }
    }
    return sol;
}

• 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