Submission #562845

#	Time	Username	Problem	Language	Result	Execution time	Memory
562845		elazarkoren	Paint By Numbers (IOI16_paint)	C++17	7 / 100	1 ms	304 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 2e5;
const int MAX_K = 105;

int cnt[MAX_N];
//bool dpl[MAX_N][MAX_K];
//bool dpr[MAX_N][MAX_K];

std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n = s.size();
    int k = c.size();
//    for (int i = 0; i < n; i++) {
//        int sum = -1;
//        for (int j = 0; j < k; j++) {
//            sum += c[j] + 1;
//            if (i && dpl[i - 1][j]) {
//                dpl[i][j] = true;
//                continue;
//            }
//            if (sum > i + 1) break;
//        }
//    }
    vi bad;
    for (int i = 0; i < n; i++) {
        if (s[i] == '_') bad.push_back(i);
    }
    bad.push_back(n);
    int sum = 0;
    for (int d : c) sum += d;
    int count = 0;
    for (int j = 0; j <= n; j++, count++) {
        int ind = j;
        int x = 0;
        for (int l = 0; l < k && ind < n; l++) {
            int d = c[l];
            while (ind < n) {
                int y = *lower_bound(all(bad), ind);
                if (y - ind >= d) break;
                ind = y + 1;
            }
            for (int i = ind; i < min(ind + d, n); i++) {
                x++, cnt[i]++;
            }
            ind += d + 1;
        }
        if (x != sum - k + 1) {
            for (int l = 0; l < k && ind < n; l++) {
                int d = c[l];
                while (ind < n) {
                    int y = *lower_bound(all(bad), ind);
                    if (y >= d) break;
                    ind = y + 1;
                }
                for (int i = ind; i < min(ind + d, n); i++) {
                    cnt[i]--;
                }
                ind += d + 1;
            }
            break;
        }
//        ind = n - 1;
//        for (int l = k - 1; l >= j; l--) {
//            int d = c[l];
//            for (int i = ind; i > ind - d; i--) cnt[i]++;
//            ind -= d + 1;
//        }
    }
    string ans(n, '?');
    for (int i = 0; i < n; i++) {
        if (cnt[i] == count) ans[i] = 'X';
        else if (!cnt[i]) ans[i] = '_';
    }
    return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10