Submission #1284602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284602		gustavo_d	Paint By Numbers (IOI16_paint)	C++20	59 / 100	1 ms	348 KiB

paint

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

#define sz(x) (int)(x).size()

const int MAXN = 100;
const int INF = 1e9;

string s; vector<int> rngSzs;
int n, k;

int addMax(int l, int r, int rngPt) {
    if (rngPt == k) return k;
    for (int i=l, open=0; i<=r; i++) {
        if (s[i] == '_') {
            open = 0;
            continue;
        }
        open++;
        if (open == rngSzs[rngPt]) {
            rngPt++;
            if (rngPt == k) return k;
            open = 0; i++;
            continue;
        }
    }
    return rngPt;
}

string solve_puzzle(string S, vector<int> C) {
    s = S; rngSzs = C;
    n = sz(s), k = sz(rngSzs);

    string ans;
    for (int i=0; i<n; i++) {
        bool white = false, black = false;

        if (addMax(i+1, n-1, addMax(0, i-1, 0)) == k) white = true;
        for (int rng=0; rng<k; rng++) {
            // use [0, rng-1] in [0, i-1]
            int blocked = -1;
            for (int r=0; r<rng; r++) {
                for (int i=blocked+1, open=0; ; i++) {
                    if (s[i] == '_') {
                        open = 0;
                        continue;
                    }
                    open++;
                    if (open == rngSzs[r]) {
                        blocked = i+1;
                        break;
                    }
                }
            }

            // if (i == 3 and rng == 1) cout << blocked << endl;

            int open = 0;
            for (int j=i; j>blocked; j--) {
                if (s[j] == '_') break;
                open++;
            }

            if (open == 0) continue;

            open = min(open, rngSzs[rng]);

            bool can = i - open + rngSzs[rng] < n;
            for (int j=i; can and j<=i-open+rngSzs[rng]; j++) {
                if (s[j] == '_') can = false;
            }

            if (can and addMax(i - open + rngSzs[rng] + 2, n-1, rng+1) == k) {
                // if (i == 3) cout << open << ' ' << rng << endl;
                black = true;
                break;
            }
        }

        if (white and black) ans += '?';
        else ans += (white ? '_' : 'X');
    }

    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: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10