Submission #592209

#	Time	Username	Problem	Language	Result	Execution time	Memory
592209		AlperenT	Paint By Numbers (IOI16_paint)	C++17	100 / 100	658 ms	259052 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"

using namespace std;

const int N = 2e5 + 5, K = 100 + 5, INF = 1e9 + 5; 

int n, k, forcedwhite[N], forcedblack[N], posprefix[K][N], isgood[K][N], white[N], black[N], closest[K][N];

bool pos[K][N];

void update(int arr[N], int l, int r){
    arr[l]++, arr[r + 1]--;
}

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

    s = " " + s, c.insert(c.begin(), 0);

    int firstx = INF;

    for(int i = 1; i <= n; i++){
        forcedblack[i] = forcedblack[i - 1];
        forcedwhite[i] = forcedwhite[i - 1];

        if(s[i] == 'X'){
            forcedblack[i] = i;
            if(firstx == INF) firstx = i;
        }
        else if(s[i] == '_') forcedwhite[i] = i;
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++){
            if((i + 1 > n || s[i + 1] != 'X') && i - c[j] + 1 >= 1 && forcedwhite[i] < i - c[j] + 1){
                if((j == 1 && i - c[j] < firstx) || ((forcedblack[i - c[j]] <= i - c[j] - 1 && posprefix[j - 1][i - c[j] - 1] - (forcedblack[i - c[j]] == 0 ? 0 : posprefix[j - 1][forcedblack[i - c[j]] - 1])))){
                    pos[j][i] = true;
                }
            }
        }

        for(int j = 1; j <= k; j++) posprefix[j][i] = posprefix[j][i - 1] + pos[j][i];
    }

    for(int i = 1; i <= n; i++){
        if(i < forcedblack[n]) pos[k][i] = false;
        else if(pos[k][i]) isgood[k][i]++, isgood[k][i - 1]--;

        posprefix[k][i] = posprefix[k][i - 1] + pos[k][i];
    }
    
    for(int i = 1; i <= k; i++) closest[i][n + 1] = INF;

    for(int i = n; i >= 0; i--){
        for(int j = 1; j <= k; j++){
            if(pos[j][i]) closest[j][i] = i;
            else closest[j][i] = closest[j][i + 1];
        }
    }

    for(int i = n; i >= 1; i--){
        for(int j = k; j >= 1; j--){
            isgood[j][i] += isgood[j][i + 1];

            if(isgood[j][i] && pos[j][i]){
                update(black, i - c[j] + 1, i);

                if(j == k && i < n) update(white, i + 1, n);
                if(j == 1 && i - c[j] >= 1) update(white, 1, i - c[1]);
                
                if(j != 1){
                    if(forcedblack[i - c[j]] <= i - c[j] - 1){
                        isgood[j - 1][i - c[j] - 1]++;
                        if(forcedblack[i - c[j]] != 0) isgood[j - 1][forcedblack[i - c[j]] - 1]--;
                    }

                    if(closest[j - 1][forcedblack[i - c[j]]] + 1 <= i - c[j]) update(white, closest[j - 1][forcedblack[i - c[j]]] + 1, i - c[j]);
                }
            }
        }
    }

    for(int i = 1; i <= n; i++) white[i] += white[i - 1];
    for(int i = 1; i <= n; i++) black[i] += black[i - 1];

    string ans;

    for(int i = 1; i <= n; i++){
        if(s[i] == '.'){
            if(black[i] != 0 && white[i] == 0) ans += 'X';
            else if(white[i] != 0 && black[i] == 0) ans += '_';
            else ans += '?';
        }
        else ans += s[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: 10 / 10