Submission #1191211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191211		Muhammet	Paint By Numbers (IOI16_paint)	C++20	100 / 100	461 ms	61040 KiB

paint

#include "bits/stdc++.h"
#include "paint.h"
// #include "grader.cpp"

using namespace std;

#define SZ(s) (int)s.size()

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

    vector <vector <bool>> dp(n+1, vector <bool> (k+1, 0)), dp1(n+1, vector <bool> (k+1, 0)),
     dp2(n+1, vector <bool> (k+1, 0)),  dp3(n+1, vector <bool> (k+1, 0));

    vector <int> p_(n+1, 0), px(n+1, 0);
    for(int i = 0; i < n; i++) {
        p_[i] = (!i ? 0 : p_[i-1]) + (s[i] == '_');
        px[i] = (!i ? 0 : px[i-1]) + (s[i] == 'X');
    }
    vector <int> p(n+1, 0), v;
    string ans = "";
    for(int i = 0; i < n; i++) {
        ans += '_';
    }
    if(!p_[c[0]-1]) dp[c[0]-1][0] = true, v.push_back(c[0]-1), dp2[c[0]-1][0] = true;
    for(int i = c[0]; i < n; i++) {
        if(!(px[i - c[0]]) and !(p_[i] - p_[i - c[0]])) dp[i][0] = true, v.push_back(i), dp2[i][0] = true;
        if(dp[i-1][0] and s[i] != 'X') dp[i][0] = true;
    }
    if(k == 1) {
        int cnt = 0;
        for(auto i : v) {
            if(px[n-1] - px[i]) continue;
            p[i-c[0]+1]++, p[i+1]--;
            cnt++;
        }
        for(int i = 0; i < n; i++) {
            p[i] += (!i ? 0 : p[i-1]);
            if(p[i] == cnt) ans[i] = 'X';
            else if(p[i]) ans[i] = '?';
        }
        return ans;
    }
    for(int j = 1; j < k; j++) {
        for(int i = c[j] + 1; i < n; i++) {
            if(dp[i - c[j] - 1][j-1] and s[i - c[j]] != 'X' and !(p_[i] - p_[i - c[j]])) dp[i][j] = dp2[i][j] = true;
            if(dp[i-1][j] and s[i] != 'X') dp[i][j] = true;
        }
    }
    if(!(p_[n-1] - p_[n-1-c[k-1]])) dp1[n-c[k-1]][k-1] = dp3[n-c[k-1]][k-1] = true;
    for(int i = n-c[k-1]; i >= 0; i--) {
        if(!(px[n-1] - px[i + c[k-1] - 1]) and !(p_[i + c[k-1] - 1] - (!i ? 0 : p_[i-1]))) dp1[i][k-1] = dp3[i][k-1] = true;
        if(dp1[i+1][k-1] and s[i] != 'X') dp1[i][k-1] = true;
    }
    for(int j = k-2; j >= 0; j--) {
        for(int i = n-c[j]-2; i >= 0; i--) {
            if(dp1[i + c[j] + 1][j+1] and s[i + c[j]] != 'X' and !(p_[i + c[j] - 1] - (!i ? 0 : p_[i-1]))) dp1[i][j] = dp3[i][j] = true;
            if(dp1[i+1][j] and s[i] != 'X') dp1[i][j] = true;
        }
    }
    for(int j = 0; j < k-1; j++) {
        for(int i = c[j] - 1; i + 2 < n; i++) {
            if(dp2[i][j] and dp1[i + 2][j+1] and s[i+1] != 'X') p[i+1]--, p[i-c[j]+1]++;
        }
    }

    for(int i = c[k-1] - 1; i < n; i++) {
        if(dp2[i][k-1] and !(px[n-1] - px[i])) p[i+1]--, p[i-c[k-1]+1]++;
    }

    for(int i = n-1; i >= 0; i--) {
        if(dp3[i][0] and !((!i ? 0 : px[i-1]))) p[i]++, p[i+c[0]]--;
    }

    for(int i = 0; i < n; i++) {
        p[i] += (!i ? 0 : p[i-1]);
        if(p[i]) {
            ans[i] = 'X';
            for(int j = 0; j < k-1; j++) {
                if(i and i < n-1 and s[i] != 'X' and dp[i-1][j] and dp1[i+1][j+1]) ans[i] = '?';
            }
            if(i and dp[i-1][k-1] and s[i] != 'X' and !(px[n-1] - px[i])) ans[i] = '?';
            if(i < n-1 and dp1[i+1][0] and !(px[i])) ans[i] = '?';
        }
    }

    return ans;
}

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