Submission #772803

#	Time	Username	Problem	Language	Result	Execution time	Memory
772803		Sharky	Paint By Numbers (IOI16_paint)	C++17	Compilation error	0 ms	0 KiB

paint

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

const int maxn = 2e5 + 1;
const int maxk = 101;

int n, k, c[maxk], d[maxn];
string s;
bool L[maxn][maxk], R[maxn][maxk], possible[maxn][2];
int lst[maxn][maxk], nxt[maxn][maxk], lstw[maxn], nxtw[maxn], lstb[maxn], nxtb[maxn];

struct node {
    int i, j, l, r;
    node(int i, int j, int l, int r): i(i), j(j), l(l), r(r) {}
};

vector<node> b;
vector<pair<int, int>> st;

bool ok(int id) {
    return (id >= 1 && id <= n);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> s >> k;
    n = s.length();
    s = "a" + s;
    s += 'a';
    lstw[0] = lstb[0] = 0;
    nxtb[n + 1] = nxtw[n + 1] = n + 1;
    for (int i = 1; i <= n; i++) {
        lstw[i] = lstw[i - 1];
        lstb[i] = lstb[i - 1];
        if (s[i] == '_') lstw[i] = i;
        else if (s[i] == 'X') lstb[i] = i;
    }
    for (int i = n; i >= 1; i--) {
        nxtb[i] = nxtb[i + 1];
        nxtw[i] = nxtw[i + 1];
        if (s[i] == '_') nxtw[i] = i;
        else if (s[i] == 'X') nxtb[i] = i;
    }
    for (int i = 0; i <= n + 1; i++) for (int j = 0; j <= k; j++) lst[i][j] = nxt[i][j] = -1;
    for (int i = 1; i <= k; i++) cin >> c[i];
    for (int i = 0; i <= n; i++) {
        if (s[i] == 'X') break;
        lst[i][0] = i, L[i][0] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            lst[i][j] = lst[i - 1][j];
            if (s[i] == '_') continue;
            int idx = i - c[j];
            if (idx < 0 || idx > n || s[idx] == 'X' || s[i+1] == 'X') continue;
            int next_white = nxtw[idx + 1];
            if (next_white <= i) continue;
            if (idx == 0 && j > 1) continue;
            if ((idx == 0 && j == 1) || lst[idx - 1][j - 1] != -1) {
                if (!(idx == 0 && j == 1)) {
                    int pos = lst[idx - 1][j - 1];
                    int next_black = nxtb[pos + 1];
                    if (next_black <= idx) continue;
                    // cout << "debug: " << idx << ' ' << j << ' ' << lst[idx - 1][j - 1] << '\n';
                }
                L[i][j] = 1;
                lst[i][j] = i;
                b.emplace_back(i, j, idx + 1, i);
            }
            // cout << i << ' ' << j << ' ' << L[i][j] << '\n';
        }
    }
    for (int i = n + 1; i >= 1; i--) {
        if (s[i] == 'X') break;
        nxt[i][0] = i, R[i][0] = 1;
    }
    reverse(c + 1, c + k + 1);
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= k; j++) {
            nxt[i][j] = nxt[i + 1][j];
            if (s[i] == '_') continue;
            int idx = i + c[j];
            if (idx <= 0 || idx > n + 1 || s[idx] == 'X' || s[i-1] == 'X') continue;
            int last_white = lstw[idx - 1];
            if (last_white >= i) continue;
            if (idx == n + 1 && j > 1) continue;
            if ((idx == n + 1 && j == 1) || nxt[idx + 1][j - 1] != -1) {
                if (!(idx == n + 1 && j == 1)) {
                    int pos = nxt[idx + 1][j - 1];
                    int next_black = lstb[pos - 1];
                    if (next_black >= idx) continue;
                    // cout << "debug: " << idx << ' ' << j << ' ' << lst[idx - 1][j - 1] << '\n';
                }
                R[i][j] = 1;
                nxt[i][j] = i;
            }
            // cout << i << ' ' << j << ' ' << R[i][j] << '\n';
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            if (lst[i - 1][j] != -1 && nxt[i + 1][k - j] != -1 && s[i] != 'X') possible[i][0] = 1; 
        }
    }
    for (auto& [i, j, l, r] : b) {
        if (i == n && j != k) continue;
        if (i == n || (L[i][j] && s[i + 1] != 'X' && nxt[i + 2][k - j] != -1)) {
            d[l]++, d[r + 1]--;
            // cout << l << ' ' << r << '\n';
        }
    }
    for (int i = 1; i <= n; i++) {
        d[i] += d[i - 1];
        possible[i][1] = !!(d[i] > 0);
    }
    for (int i = 1; i <= n; i++) {
        if (possible[i][0] && possible[i][1]) cout << '?';
        else if (possible[i][0]) cout << '_';
        else if (possible[i][1]) cout << 'X';
        // else assert(false);
    }
    cout << '\n';
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc7D837u.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cchPmbGw.o:paint.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc7D837u.o: in function `main':
grader.cpp:(.text.startup+0x20b): undefined reference to `solve_puzzle(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status