Submission #1099879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099879		model_code	Mosaic (IOI24_mosaic)	C++17	53 / 100	122 ms	37208 KiB

mosaic

// incorrect/hazem_one_row.cpp

#include "bits/stdc++.h"
#include "mosaic.h"
using namespace std;

vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
    auto cell_index = [](int i, int j){
        return ((i < j) - (i > j)) * (max(i, j) - min(i, j));
    };
    auto next_layer = [](vector<long long> l){
        if(l.size() < 3) return vector<long long>();
        int m = (int)l.size() / 2;
        l[m] = !(l[m-1] | l[m+1]);
        l.erase(l.begin() + m + 1);
        l.erase(l.begin() + m - 1);
        m--;
        for(int i = 1; i <= m; i++){
            l[m-i] = !(l[m-i] | l[m-i+1]);
            l[m+i] = !(l[m+i] | l[m+i-1]);
        }
        return l;
    };
    auto accumulate_layer = [](vector<long long> l){
        l.insert(l.begin(), 0);
        for(int i = 1; i < (int)l.size(); i++)
            l[i] += l[i-1];
        return l;
    };

    vector<long long> layer[4];
    layer[0] = {Y.rbegin(), Y.rend()};
    layer[0].insert(layer[0].end(), X.begin()+1, X.end());
    layer[1] = next_layer(layer[0]);
    layer[2] = next_layer(layer[1]);
    layer[0] = accumulate_layer(layer[0]);
    layer[1] = accumulate_layer(layer[1]);
    layer[2] = accumulate_layer(layer[2]);
    layer[3] = accumulate_layer(layer[2]);

    auto layer_sum = [&](int i, int l, int r){
        if(r < l) return 0LL;
        int m = (int)layer[i].size() / 2;
        return layer[i][m + r] - layer[i][m + l - 1];
    };
    auto special_layers = [&](int t, int b, int l, int r){
        long long tot = 0;
        for(int k = 0; k < 3; k++){
            if(t <= k && k <= b) tot += layer_sum(k, cell_index(k, max(l, k)), cell_index(k, r));
            if(l <= k && k <= r) tot += layer_sum(k, cell_index(b, k), cell_index(max(t, k), k));
            if(t <= k && k <= b && l <= k && k <= r) tot -= layer_sum(k, 0, 0);
        }
        return tot;
    };

    vector<long long> C(T.size());
    for(int q = 0; q < (int)C.size(); q++){
        auto [t, b, l, r] = tie(T[q], B[q], L[q], R[q]);
        C[q] = special_layers(t, b, l, r);
        if(max(3, t) <= b)
            C[q] += layer_sum(2, cell_index(b, max(3, l)), cell_index(b, r));
    }
    return C;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 8
• Subtask 6: 22 / 22
• Subtask 7: 19 / 19
• Subtask 8: 0 / 22