Submission #848406

#	Time	Username	Problem	Language	Result	Execution time	Memory
848406		anha3k25cvp	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1643 ms	125696 KiB

paint

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>
#include "paint.h"

using namespace std;

const int N = 5 + 1e5;
const int inf = 7 + 1e9;

struct Event {
    int pos, val, type;
    bool operator <(const Event &O) const {
        if (pos != O.pos)
            return pos < O.pos;
        if (val != O.val)
            return val < O.val;
        return type < O.type;
    }
};

string t;
int n, m;
vector <int> a, sum, ma, vis;
vector <vector <int>> f;
vector <Event> g;

int get(int l, int r) {
    return sum[r] - (l > 0 ? sum[l - 1] : 0);
}

int cal(int i, int j) {
    if (i >= n)
        return j >= m;
    if (f[i][j] >= 0)
        return f[i][j];
    f[i][j] = 0;
    if (j < m && i + a[j] <= n && get(i, i + a[j] - 1) == 0 && t[i + a[j]] != 'X' && cal(i + a[j] + 1, j + 1)) {
        f[i][j] = 1;
        ma[i] = max(ma[i], a[j]);
        if (!vis[i + a[j]]) {
            vis[i + a[j]] = 1;
            g.push_back({i + a[j], 1, 0});
            g.push_back({i + a[j] + 1, -1, 0});
        }
    }
    if (t[i] != 'X' && cal(i + 1, j)) {
        f[i][j] = 1;
        if (!vis[i]) {
            vis[i] = 1;
            g.push_back({i, 1, 0});
            g.push_back({i + 1, -1, 0});
        }
    }
    return f[i][j];
}

string solve_puzzle(string s, vector<int> c) {
    n = s.size(); m = c.size();
    s += '_';
    t = s;
    a = c;
    sum.assign(n, 0);
    for (int i = 0; i < n; i ++) {
        sum[i] = s[i] == '_';
        if (i > 0)
            sum[i] += sum[i - 1];
    }
    ma.assign(n, 0);
    vis.assign(n + 1, 0);
    f.assign(n + 2, vector <int> (m + 1, -1));
    cal(0, 0);
    for (int i = 0; i < n; i ++)
        if (ma[i]) {
            g.push_back({i, 1, 1});
            g.push_back({i + ma[i], -1, 1});
        }
    string ans;
    int pos = 0;
    sort(g.begin(), g.end());
    vector <int> cnt(2, 0);
    for (int i = 0; i < n; i ++) {
        while (pos < g.size() && g[pos].pos == i) {
            cnt[g[pos].type] += g[pos].val;
            pos ++;
        }
        if (cnt[0] == 0)
            ans += 'X';
        else if (cnt[1] == 0)
            ans += '_';
        else
            ans += '?';
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:87:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         while (pos < g.size() && g[pos].pos == i) {
      |                ~~~~^~~~~~~~~~

• 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