Submission #609518

#	Time	Username	Problem	Language	Result	Execution time	Memory
609518		Mohammed_Atalah	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	308 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 && j  < csz; i++) {
        if (s[i] == '_') {
            curr = 0;
            continue;
        } else {
            curr++;
        }

        // cout << curr  << " " << i << endl;
        if (curr == c[j]) {
            start[j] = i - c[j] + 1;
            j++;
            curr = -1;
        }
    }

    // cout << start[1] << " " << end[1] << endl;

    for (int i = 0; i < csz; i++) {
        if (start[i] == end[i] && start[i] + c[i] < n) {
            s[start[i] + c[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;
    vector<vector<int>> v2;
    for (int i = 0; i < csz; i++) {
        v.push_back({start[i], c[i]});
        v2.push_back({end[i] + 1, c[i]});
    }
    sort(v.begin(), v.end());
    sort(v2.begin(), v2.end());
    set<int> ss;
    map<int, int> mp;
    j = 0;
    int j2 = 0;
    bool can = true;
    // cout << start[1] << " " << end[1] << endl;
    for (int i = 0; i < n ; i++) {
        if (j < csz && v[j][0] == i) {
            ss.insert(v[j][1]);
            mp[v[j][1]]++;
            j++;
        }
        if (j2 < csz && v2[j2][0] == i) {
            mp[v2[j2][1]]--;
            if (mp[v2[j2][1]] == 0) {

                ss.erase(ss.lower_bound(v2[j2][1]));
            }
            j2++;
        }
        if (s[i] == '_' || s[i] == 'X') {
            can =  1;
            continue;
        }
        if ((i == 0 && s[i] == '.') || (i > 0 && s[i] == '.' && s[i - 1] == '_')) {
            auto it = white.lower_bound(i);
            int e = n;
            if (it != white.end()) {
                e = *it;
            }
            e = e - i;
            // cout << e << endl;
            auto itt = ss.upper_bound(e);
            if ((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: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10