Submission #591698

#	Time	Username	Problem	Language	Result	Execution time	Memory
591698		kamelfanger83	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	296 KiB

paint

#include "paint.h"

#include <vector>
#include <string>
#include <functional>
#include <limits>
#include <algorithm>
#include <cassert>

using namespace std;
struct segtree{
    vector<int> cache;
    function<int(int, int)> conquer;
    int neutral;
    segtree(int n, function<int(int, int)> conquera, int neutrala){
        cache = vector<int> (n*4);
        conquer = conquera;
        neutral = neutrala;
    }
    int build(int l, int r, int i, vector<int>& v){
        if(l+1==r) return cache[i] = v[l];
        int m = l + (r-l)/2;
        return cache[i] = conquer(build(l, m, i*2+1, v), build(m, r, i*2+2, v));
    }
    int query(int l, int r, int i, int ql, int qr){
        if(ql <= l && r <= qr) return cache[i];
        if(qr <= l || r <= ql) return neutral;
        int m = l + (r-l)/2;
        return conquer(query(l, m, i*2+1, ql, qr), query(m, r, i*2+2, ql, qr));
    }
};



string solve_puzzle(string s, vector<int> c) {
    int k = c.size();
    int n = s.size();
    auto add  = [&](int a, int b) ->int {return a + b;};
    auto minf = [&](int a, int b) ->int {return min(a, b);};
    segtree sum (k, add, 0);
    sum.build(0, k, 0, c);
    segtree mint (k, minf, numeric_limits<int>::max());
    mint.build(0, k, 0, c);
    vector<int> back_cram = {k};
    vector<int> occ = {n};
    int tsize = 0;
    int at = k-1;
    for(int back = n-1; back >= 0; back--){
        if(s[back] == '_'){
            occ.push_back(back);
            while(at >= 0 && tsize >= c[at]){
                tsize -= c[at] + 1;
                at--;
            }
            tsize = 0;
            back_cram.push_back(at+1);
        }
        else tsize++;
    }
    occ.push_back(-1);
    reverse(back_cram.begin(), back_cram.end());
    reverse(occ.begin(), occ.end());
    int maxdone = 0;
    int bi = 0;
    for(int solver = 0; solver < n; solver++){
        if(s[solver] != '.'){
            int tsize = occ[bi+1]-occ[bi]-1;
            while(maxdone < k && tsize >= c[maxdone]){
                tsize -= c[maxdone];
                tsize -= 1;
                maxdone++;
            }
            bi++;
            continue;
        }
        bool w = false, b = false;
        if(maxdone >= back_cram[bi]){
            w = true;
            if(occ[bi+1]-occ[bi] - 1 >= mint.query(0, k, 0, back_cram[bi]-1, maxdone+1)) b = true;
        }
        else{
            int l = maxdone;
            int r = back_cram[bi] + 1;
            while(l+1<r){
                int m = l + (r-l)/2;
                int prened = sum.query(0, k, 0, maxdone, m) + (m-maxdone-1);
                int preav = solver-occ[bi]-1;
                if(prened > preav) r = m;
                else l = m;
            }
            int prened = max(0,sum.query(0, k, 0, maxdone, l) + (l-maxdone-1));
            int qans = sum.query(0, k, 0, l, back_cram[bi]);
            int postned = max(0,sum.query(0, k, 0, l, back_cram[bi]) + (back_cram[bi]-l-1));
            int preav = solver-occ[bi]-1;
            int postav = occ[bi+1]-solver-1;
            if(prened <= preav && postned <= postav){
                w = true;
            }
            if(prened + postned + 1 < occ[bi+1]-occ[bi]-1 || occ[bi]+prened + 1 < solver || prened == 0 || postned == 0) b = true;
        }
        if(w && b) s[solver] = '?';
        else if(w) s[solver] = '_';
        else if(b) s[solver] = 'X';
        else assert(false);
    }
    return s;
}

/*
#include "paint.h"

#include <vector>
#include <string>
#include <cstdio>
#include <cassert>

const int S_MAX_LEN = 200 * 1000;
char buf[S_MAX_LEN + 1];

int main() {
    assert(1 == scanf("%s", buf));
    std::string s = buf;
    int c_len;
    assert(1 == scanf("%d", &c_len));
    std::vector<int> c(c_len);
    for (int i = 0; i < c_len; i++) {
        assert(1 == scanf("%d", &c[i]));
    }
    std::string ans = solve_puzzle(s, c);


    printf("%s\n", ans.data());
    return 0;
}
*/

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:92:17: warning: unused variable 'qans' [-Wunused-variable]
   92 |             int qans = sum.query(0, k, 0, l, back_cram[bi]);
      |                 ^~~~

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