Submission #1180196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180196		HappyCapybara	Paint By Numbers (IOI16_paint)	C++20	90 / 100	2094 ms	28512 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
using namespace std;

int n;
vector<bool> st;

void update(int pos, int node=1, int tl=0, int tr=n-1){
    if (tl == tr){
        st[node] = true;
        return;
    }
    int tm = (tl+tr)/2;
    if (pos <= tm) update(pos, node*2, tl, tm);
    else update(pos, node*2+1, tm+1, tr);
    st[node] = st[node*2] | st[node*2+1];
}

bool query(int l, int r, int node=1, int tl=0, int tr=n-1){
    if (l <= tl && tr <= r) return st[node];
    int tm = (tl+tr)/2;
    if (l <= tm && query(l, r, node*2, tl, tm)) return true;
    if (tm+1 <= r && query(l, r, node*2+1, tm+1, tr)) return true;
    return false;
}

string solve_puzzle(string s, vector<int> c){
    //cout << "a" << endl;
    int k = c.size();
    n = s.size();
    st.resize(4*n, false);
    for (int i=0; i<n; i++){
        if (s[i] == '_') update(i);
    }
    vector<vector<bool>> dpl(n+2, vector<bool>(k+1, false)), dpr(n+2, vector<bool>(k+1, false));
    //cout << "b" << endl;
    for (int j=0; j<=k; j++){
        for (int i=0; i<=n+1; i++){
            if (i <= 1){
                if (j == 0) dpr[i][j] = true;
                else dpr[i][j] = false;
                continue;
            }
            if (j == 0){
                if (s[i-2] != 'X') dpr[i][j] = dpr[i-1][j];
                continue;
            }
            if ((s[i-2] == 'X' || s[i-2] == '.') && i-2-c[j-1]+1 >= 0 && !query(i-2-c[j-1]+1, i-2) && (i-2-c[j-1] == -1 || s[i-2-c[j-1]] != 'X') && dpr[i-c[j-1]-1][j-1]) dpr[i][j] = true;
            if ((s[i-2] == '_' || s[i-2] == '.') && dpr[i-1][j]) dpr[i][j] = true;
        }
    }
    //cout << "c" << endl;
    vector<pair<int,int>> pos;
    for (int j=k; j>=0; j--){
        for (int i=n+1; i>=0; i--){
            if (i >= n){
                if (j == k) dpl[i][j] = true;
                else dpl[i][j] = false;
                continue;
            }
            if (j == k){
                if (s[i] != 'X') dpl[i][j] = dpl[i+1][j];
                continue;
            }
            if ((s[i] == 'X' || s[i] == '.') && i+c[j]-1 < n && !query(i, i+c[j]-1) && (i+c[j] == n || s[i+c[j]] != 'X') && dpl[i+c[j]+1][j+1]){
                dpl[i][j] = true;
                if ((i == 0 && j == 0) || (s[i-1] != 'X' && ((i == 1 && j == 0) || dpr[i-2+2][j]))) pos.push_back({i, i+c[j]-1});
            }
            if ((s[i] == '_' || s[i] == '.') && dpl[i+1][j]) dpl[i][j] = true;
        }
    }
    /*for (int i=0; i<=n+1; i++){
        for (int j=0; j<=k; j++) cout << dpr[i][j];
        cout << endl;
    }*/
    string res = s;
    for (int i=0; i<n; i++){
        if (s[i] == '.'){
            for (int j=0; j<=k; j++){
                if (dpl[i+1][j] && dpr[i-1+2][j]) res[i] = '_';
            }
        }
    }
    //cout << res << endl;
    sort(pos.begin(), pos.end());
    int cur = 0;
    for (auto [l, r] : pos){
        //cout << l << " " << r << endl;
        for (int i=max(l, cur); i<=r; i++){
            if (s[i] == '.'){
                if (res[i] == '_' || res[i] == '?') res[i] = '?';
                else res[i] = 'X';
            }
        }
    }
    return res;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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