Submission #570968

#	Time	Username	Problem	Language	Result	Execution time	Memory
570968		definitelynotmee	Paint By Numbers (IOI16_paint)	C++98	100 / 100	405 ms	163612 KiB

paint

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using ll = long long;
using pii = pair<int,int> ;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const int INF =(1<<30)-1;

std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n = s.size(), k = c.size();

    vector<pii> nextblank(n,{-1,n}), nextfull(n,{-INF,INF});
    
    int lastb = -1, lastf = -INF;
    for(int i = 0; i < n; i++){
        if(s[i] == '_')
            lastb = i;
        else if(s[i] == 'X')
            lastf = i;
        nextblank[i].ff = lastb;
        nextfull[i].ff = lastf;
    }
    lastb = n;
    lastf = INF;
    for(int i = n-1; i >= 0; i--){
        if(s[i] == '_')
            lastb = i;
        else if(s[i] == 'X')
            lastf = i;
        nextblank[i].ss = lastb;
        nextfull[i].ss = lastf;
    }

    matrix<int> canpref(k,vector<int>(n)), cansuf(k,vector<int>(n));
    for(int i = 0; i < n; i++){
        if(nextblank[i].ff <= i-c[0]&& (i-c[0] == -1 || nextfull[i-c[0]].ff == -INF)){
            canpref[0][i] = 1;
        }
        if(s[i]!='X' && i){
            canpref[0][i]|=canpref[0][i-1];
        }
    }
    for(int i = n-1; i >= 0; i--){
        if(nextblank[i].ss >= i+c[k-1] && (i+c[k-1] == n || nextfull[i+c[k-1]].ss == INF)){
            cansuf[k-1][i] = 1;
        }
        
        if(s[i]!='X' && i != n-1){
            cansuf[k-1][i]|=cansuf[k-1][i+1];
        }
    }
    

    for(int i = 1; i < k; i++){
        for(int j = c[i]+1; j < n; j++){
            if(nextblank[j].ff <= j-c[i]){
                canpref[i][j] = canpref[i-1][j-c[i]-1]&&s[j-c[i]]!='X';
            }
            if(s[j]!='X'){
                canpref[i][j]|=canpref[i][j-1];
            }
        }
    }

    for(int i = k-2; i >= 0; i--){
        for(int j = n-c[i]-2; j >= 0; j--){
            if(nextblank[j].ss >= j+c[i]){
                cansuf[i][j] = cansuf[i+1][j+c[i]+1]&&s[j+c[i]]!='X';
            }
            if(s[j]!='X'){
                cansuf[i][j]|=cansuf[i][j+1];
            }
        }
    }
    vector<int> can0(n), can1(n);

    for(int i = 0; i < n-2; i++){
        can0[i] = cansuf[0][i+1]&&nextfull[i].ff == -INF;
    }
    for(int i = 1; i < n; i++){
        can0[i] |= canpref[k-1][i-1] && nextfull[i].ss == INF;
    }

    for(int i = 1; i < n-1; i++){
        for(int j = 0; j < k-1; j++){
            can0[i]|=canpref[j][i-1]&&cansuf[j+1][i+1];
        }
    }

    vector<int> delta(n+1);

    if(k == 1){
        for(int i = 0; i+c[0]-1 < n; i++){
            int l = i, r = i+c[0]-1;
            if(nextblank[i].ss > r && (i == 0 || nextfull[i-1].ff == -INF) && (r == n-1 || nextfull[r+1].ss == INF))
                delta[l]++, delta[r+1]--;
        }
    } else{
        for(int i = 0; i+c[0]+1 < n; i++){
            int l = i, r = i+c[0]-1;
            if(nextblank[i].ss > r && (i == 0 || nextfull[i-1].ff == -INF) && s[r+1] !='X' && cansuf[1][r+2])
                delta[l]++, delta[r+1]--;//, cout << l << ' ' << r << ' ' << 'a'<< '\n';
        }
        for(int i = 2; i+c[k-1]-1 < n; i++){
            int l = i, r = i+c[k-1]-1;
            if(nextblank[i].ss > r && (r == n-1 || nextfull[r+1].ss == INF) && s[l-1] !='X' && canpref[k-2][l-2])
                delta[l]++, delta[r+1]--;//, cout << l << ' ' << r << ' ' << 'b'<< '\n';
        }
        for(int i = 1; i < k-1; i++){
            for(int j = 2; j+c[i]+1 < n; j++){
                int l = j, r = j+c[i]-1;
                if(nextblank[l].ss > r && s[l-1] != 'X' && s[r+1]!='X' && canpref[i-1][l-2] && cansuf[i+1][r+2])
                    delta[l]++, delta[r+1]--;//, cout << l << ' ' << r << ' ' << 'c' << '\n';
            }
        }
    }

    int cur = 0;
    for(int i = 0; i < n; i++){
        cur+=delta[i];
        if(cur)
            can1[i] = 1;
    }

    string resp(n,0);
    for(int i = 0; i < n; i++){
        if(s[i] == 'X')
            can0[i] = 0;

        if(can0[i]){
            if(can1[i]){
                resp[i] = '?';
            } else {
                resp[i] = '_';
            }
        } else {
            resp[i]= 'X';
        }
    }
    

    return resp;

}

• 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: 10 / 10