제출 #706405

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706405		rafatoa	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2076 ms	177044 KiB

paint

#include <bits/stdc++.h>
using namespace std;
 
struct ST{
    int N;
    vector<int> tree;
    ST(int n){
        N = (1LL<<(int)ceil(log2(n)));
        tree = vector<int>(2*N);
    }
 
    void update(int k, int val){
        k += N;
        tree[k] += val;
        for(k /= 2; k >= 1; k /= 2)
            tree[k] = tree[2*k]+tree[2*k+1];
    }
 
    int query(int a, int b){
        a += N, b += N;
        int ans = 0;
        while(a <= b){
            if(a%2 == 1) ans += tree[a++];
            if(b%2 == 0) ans += tree[b--];
            a /= 2, b /= 2;
        }
        return ans;
    }
};
 
string solve_puzzle(string s, vector<int> c){
    if(s.size() == 1) return "X"; //Caso bomba :)
 
    int n = s.size(), k = c.size();
    c.insert(c.begin(), 0); //Pasar c a 1-index
    c.push_back(0);
 
    vector<int> pw(n+1), pb(n+1);
    for(int i=0; i<n; i++){
        pw[i+1] = pw[i]+(s[i] == '_' ? 1 : 0);
        pb[i+1] = pb[i]+(s[i] == 'X' ? 1 : 0);
    }
 
    //
    auto wh = [&](int l, int r){
        return pw[r+1]-pw[l];
    };
    auto bl = [&](int l, int r){
        return pb[r+1]-pb[l];
    };
 
    //
    vector<vector<int>> l(n, vector<int>(k+2)), r(n, vector<int>(k+2));
    for(int i=0; i<n; i++){
        if(bl(0, i) == 0) l[i][0] = 1;
        if(bl(i, n-1) == 0) r[i][k+1] = 1;
    }
 
    for(int j=1; j<=k; j++)
    for(int i=0; i<n; i++){
        if(i-1 >= 0 && s[i] != 'X') l[i][j] |= l[i-1][j];
        if(i+c[j]-1 < n && ((i-2 < 0 && j == 1) || (i-2 >= 0 && l[i-2][j-1])) &&
        wh(i, i+c[j]-1) == 0 && (i-1 < 0 || s[i-1] != 'X') && (i+c[j] >= n || s[i+c[j]] != 'X')){
            //cerr << i+c[j]-1 << " " << j << "\n";
            l[i+c[j]-1][j] = 1;
        }
    }
    
    for(int j=k; j>=1; j--)
    for(int i=n-1; i>=0; i--){
        if(i+1 < n && s[i] != 'X') r[i][j] |= r[i+1][j];
        if(i-c[j]+1 >= 0 && ((i+2 >= n && j == k) || (i+2 < n && r[i+2][j+1])) &&
        wh(i-c[j]+1, i) == 0 && (i+1 >= n || s[i+1] != 'X') && (i-c[j] < 0 || s[i-c[j]] != 'X')){
            //cerr << i-c[j]+1 << " " << j << "\n";
            r[i-c[j]+1][j] = 1;
        }
    }
 
    string ans = string(n, '?');
    for(int i=0; i<n; i++){
        bool ok = 0;
        if(i == 0) ok = r[i+1][1];
        else if(i == n-1) ok = l[i-1][k];
        else {
            for(int j=0; j<=k && !ok; j++)
                ok |= (l[i-1][j] && r[i+1][j+1]);
        }
 
        if(!ok || s[i] == 'X') ans[i] = 'X';
    }
 
    ST st(n+1);
    for(int j=1; j<=k; j++)
    for(int i=0; i<n; i++){
        if(i+c[j]-1 < n && ((i-2 < 0 && j == 1) || (i-2 >= 0 && l[i-2][j-1])) && ((i+c[j]+1 >= n && j == k) || (i+c[j]+1 < n && r[i+c[j]+1][j+1])) &&
        (i-1 < 0 || s[i-1] != 'X') && (i+c[j] >= n || s[i+c[j]] != 'X') && wh(i, i+c[j]-1) == 0){
            st.update(i, 1); st.update(i+c[j], -1);
        }
    }
 
    for(int i=0; i<n; i++)
        if(st.query(0, i) == 0 || s[i] == '_') ans[i] = '_';
    return ans;
}

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