Submission #1006056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006056		Mr_Husanboy	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 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] ++;
                x[j + c[i]] --;
            }
        }       
    }
    
    for(int j = 1; j <= n; j ++){
        x[j] += x[j - 1];
    }
    debug(x);
    debug(rig);
    for(int i = 0; i <= k; i ++){
        vector<int> near(n + 2, -1);
        if(rig[i + 1][n + 1]) near[n + 1] = n + 1;
        for(int j = n; j >= 1; j --){
            near[j] = (rig[i + 1][j] ? j : near[j + 1]);
        }
        vector<int> lnear(n + 2, -1);
        if(i == 0) lnear[0] = 0;
        for(int j = 1; j <= n; j ++){
            lnear[j] = lef[i][j] ? j : lnear[j - 1];
        }
        for(int j = 1; j <= n; j ++){
            if(lnear[j - 1] != -1 && near[j + 1] != -1 && b[near[j + 1] - 1] - b[lnear[j - 1]] == 0){
                debug(i, j, near[j + 1]);
                _[lnear[j - 1] + 1] ++;
                _[near[j + 1]] --;
            }
        }
    }
    for(int i = 1; i <= n; i ++) _[i] += _[i - 1];
    string ans = "";
    for(int i = 1; i <= n; i ++) if(_[i] && x[i]) ans.push_back('?'); else if(_[i]) ans.push_back('_'); else ans.push_back('X');
 
    return ans;
}

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