Submission #1005849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005849		Mr_Husanboy	Paint By Numbers (IOI16_paint)	C++17	0 / 100	2 ms	604 KiB

paint

#include "paint.h"

#include <cstdlib>
#include<bits/stdc++.h>
#ifdef LOCAL
#include "debugger.cpp"
#else
#define debug(...)
#endif

using namespace std;
#define all(a) (a).begin(), (a).end()



string solve_puzzle(string s, vector<int> c) {
    int n = s.size();
    int k = c.size();
    s = "$" + s + "$";
    reverse(all(c)); c.push_back(0); reverse(all(c)); c.push_back(0);
    vector lef(k + 2, vector(n + 2, false)), rig(k + 2, vector(n + 2, false));
    lef[0][0] = 1;
    for(int i = 1; i <= n; i ++){
        if(s[i] == 'X') break;
        lef[0][i] = 1;
    }

    vector<int> w(n + 2), b(n + 2);
    for(int i = 1; i <= n; i ++) w[i] = w[i - 1] + (s[i] == '_'), b[i] = b[i - 1] + (s[i] == 'X');

    for(int i = 1; i <= k; i ++){
        vector<int> near(n + 2, -1);
        if(i == 1) near[0] = 0;
        for(int j = 1; j <= n; j ++) near[j] = (lef[i - 1][j] ? j : near[j - 1]);
        debug(near);
        for(int j = c[i]; j <= n; j ++){
            if(j == c[i]){
                if(i == 1) lef[i][j] = 1;
            }else{
                if(w[j] - w[j - c[i]] == 0 && near[j - c[i] - 1] != -1 && b[j - c[i]] - b[near[j - c[i] - 1]] == 0){
                    debug(i, j, c[i]);
                    lef[i][j] = 1;
                }
            }
        }
    }
    debug(lef);
    rig[k + 1][n + 1] = 1;
    for(int i = n; i >= 1; i --){
        if(s[i] == 'X') break;
        rig[k + 1][i + 1] = 1;
    }
    for(int i = k; i >= 1; i --){
        vector<int>near(n + 2, -1);
        if(i == k) near[n + 1] = n + 1;
        for(int j = n; j >= 1; j --) near[j] = (rig[i + 1][j] ? j : near[j + 1]);
        for(int j = n - c[i] + 1; j >= 1; j --){
            if(j + c[i] - 1 == n){
                if(i == k) rig[i][j] = 1;
            }else{
                if(w[j + c[i] - 1] - w[j - 1] == 0 && near[j + c[i] + 1] != -1 && b[near[j + c[i] + 1] - 1] - b[j + c[i]] == 0){
                    rig[i][j] = 1;
                }
            }
        }
    }


    vector<int> x(n + 2), _(n + 2);
    for(int i = 1; i <= k; i ++){
        for(int j = 1; j + c[i] - 1 <= n; j ++){
            if(lef[i][j + c[i] - 1] && rig[i][j]){
                x[j] = 1;
                x[j + c[i]] = -1;
            }
        }       
    }
    
    for(int j = 1; j <= n; j ++){
        x[j] += x[j - 1];
    }

    
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:84:1: warning: no return statement in function returning non-void [-Wreturn-type]
   84 | }
      | ^

• 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