Submission #851719

#	Time	Username	Problem	Language	Result	Execution time	Memory
851719		ntkphong	Paint By Numbers (IOI16_paint)	C++14	100 / 100	183 ms	176220 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
 
const int mxN = 2e5 + 10;
int dpL[mxN][100 + 10], dpR[mxN][100 + 10];
 
string solve_puzzle(string s, vector<int> c) {
    
    int m = c.size();
    int n = s.size();
    
    s = ' ' + s;
    c.insert(c.begin(), 0);
    
    vector<int> sum(n + 10);
    vector<int> d(n + 10, 0);
    vector<int> check(n + 10, 0);
    
    for(int i = 1; i <= n; i ++) sum[i] = sum[i - 1] + (s[i] == '_');
        
    auto get = [&](int l, int r) {
        return sum[r] - sum[l - 1];
    };
    
    dpR[n + 1][m] = 1;
    for(int i = n; i >= 1; i --) {
        for(int j = 0; j <= m; j ++) {
            if(!dpR[i + 1][j]) continue ;
            
            if(s[i] != 'X') dpR[i][j] = 1;
            if(j > 0 && i - c[j] > 0 && s[i - c[j]] != 'X' && get(i - c[j] + 1, i) == 0) {
                dpR[i - c[j]][j - 1] = 1;
            }
        }
    }
    
    dpL[0][1] = 1;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m + 1; j ++) {
            
            if(!dpL[i - 1][j]) continue ;
            
            if(j <= m && i + c[j] == n + 1 && get(i, n) == 0) {
                if(dpR[i + c[j]][j]) {
                    d[i] ++ ;
                    d[i + c[j]] -- ;
                }
            }  else 
            
            if(j <= m && i + c[j] <= n && s[i + c[j]] != 'X' && get(i, i + c[j] - 1) == 0) {
                if(dpR[i + c[j]][j]) {
                    d[i] ++ ;
                    d[i + c[j]] -- ;
                }
            }
            
            if(s[i] != 'X') dpL[i][j] = 1;
            
            if(j <= m && i + c[j] <= n && s[i + c[j]] != 'X' && get(i, i + c[j] - 1) == 0) {
                dpL[i + c[j]][j + 1] = 1;
            }
        }
        
        for(int j = 1; j <= m; j ++) {
            if(s[i] == '.') {
                check[i] = check[i] || (dpL[i][j] && dpR[i][j - 1]) 
                        || (dpL[i][j + 1] && dpR[i][j]);
            
            }
        }
    }
    
    string str = "";
    
    for(int i = 1; i <= n; i ++) {
        d[i] += d[i - 1];
        
        if(s[i] == '.') {
            if(check[i] && d[i]) str += '?'; else
            if(check[i]) str += '_'; else 
            str += 'X';
        } else
            str += s[i];
    }
  
    return str;
}

• 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