Submission #851715

#	Time	Username	Problem	Language	Result	Execution time	Memory
851715		ntkphong	Paint By Numbers (IOI16_paint)	C++14	0 / 100	1 ms	2392 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 + 1);
    vector<int> d(n + 1, 0);
    vector<int> check(n + 1, 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];
    }
    
    for(int i = 1; i <= n; i ++) cout << d[i] << " "; cout << "\n";
    for(int i = 1; i <= n; i ++) cout << check[i] << " "; cout << "\n";
    
    return str;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:87:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   87 |     for(int i = 1; i <= n; i ++) cout << d[i] << " "; cout << "\n";
      |     ^~~
paint.cpp:87:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   87 |     for(int i = 1; i <= n; i ++) cout << d[i] << " "; cout << "\n";
      |                                                       ^~~~
paint.cpp:88:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   88 |     for(int i = 1; i <= n; i ++) cout << check[i] << " "; cout << "\n";
      |     ^~~
paint.cpp:88:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   88 |     for(int i = 1; i <= n; i ++) cout << check[i] << " "; cout << "\n";
      |                                                           ^~~~

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