Submission #609454

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

paint

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

std::string solve_puzzle(std::string s, std::vector<int> c) {

    int n = s.size();
    int csz = c.size();
    vector<int> end(csz);
    vector<int> start(csz);
    int curr = 0;
    int j = csz - 1;
    set<int> white;

    for (int i = 0; i < n ; i++) {
        if (s[i] == '_') {
            white.insert(i);
        }
    }

    for (int i = n - 1; i >= 0 && j >= 0; i--) {
        if (s[i] == '_') {
            curr = 0;
        } else {
            curr++;
        }

        if (curr == c[j]) {
            end[j] = i;
            j--;
            curr = -1;
        }
    }
    curr = 0;
    j = 0;
    for (int i = 0; i < n - 1 && j  < csz; i++) {
        if (s[i] == '_') {
            curr = 0;
            continue;
        } else {
            curr++;
        }

        if (curr == c[j]) {
            start[j] = i - c[j] + 1;
            j++;
            curr = -1;
        }
    }



    for (int i = 0; i < csz; i++) {
        if (start[i] + c[i] - 1 >= end[i]) {
            for (int j = end[i]; j <= start[i] + c[i] - 1; j++) {
                s[j] = 'X';
            }
        }
    }
    vector<vector<int>> v;
    for (int i = 0; i < csz; i++) {
        v.push_back({start[i], c[i]});
    }
    sort(v.begin(), v.end());
    set<int> ss;
    j = 0;
    bool can = true;
    // cout << start[0] << " " << end[0] << endl;
    for (int i = 0; i < n ; i++) {
        if (s[i] == '_' || s[i] == 'X') {
            can =  1;
            continue;
        }
        if (j < csz && v[j][0] == i) {
            ss.insert(v[j][1]);
            j++;
        }
        if ((i == 0 && s[i] == '.') || (i > 0 && s[i] == '.' && s[i - 1] == '_')) {
            auto it = white.lower_bound(i);
            int e = n - 1;
            if (it != white.end()) {
                e = *it;
            }
            e = e - i;
            auto itt = ss.upper_bound(e);
            if ((itt == ss.end() && ss.size() == 0) || (itt == ss.begin())) {
                can = false;
            }
        }
        if (!can) {
            s[i] = '_';
        }
    }

    for (int i = 0 ; i < n ; i++) {
        if (s[i] == '.') {
            s[i] = '?';
        }
    }

    return s;
}

• 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