Submission #293757

#	Time	Username	Problem	Language	Result	Execution time	Memory
293757		Aldas25	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	384 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

int fr[110], to[110];
bool dp[200100][110];
int rEnd[110];

bool possBlack (int x, int y, string s) {
    if (y < x || x < 0 || y >= (int)s.size())
        return false;
    FOR(i, x, y)
        if (s[i] == '_')
            return false;
    return true;
}

bool possWhite (int x, int y, string s) {
    if (y < x || x < 0 || y >= (int)s.size())
        return false;
    FOR(i, x, y)
        if (s[i] == 'X')
            return false;
    return true;
}

bool possWhite (int x, string s) {
    return possWhite(x, x, s);
}

bool isDp (int toId, int jId) {
    if (jId < 0) return true;
    if (toId < 0) return false;
    FOR(i, 0, toId)
        if (dp[i][jId])
            return true;
    return false;
}

bool endsAft (int i, int j, int k, int n){
    if (j >= k) return true;
    if (rEnd[j] >= i) return true;
    else return false;
}

bool canWh[200100];

std::string solve_puzzle(std::string s, std::vector<int> c) {
    string ret = s;
    int n = (int)s.size();
    int k = (int)c.size();

    FOR(i, 0, k-1) fr[i] = 0, to[i] = n;

    int cur = n;
    for (int j = k-1; j >= 0; j--) {
        cur -= c[j];
        while (true) {
            bool ok = true;
            if (j < k-1 && !possWhite(cur+c[j], s)) ok = false;
            if (j > 0 && !possWhite(cur-1, s)) ok = false;
            if (!possBlack(cur, cur+c[j]-1, s)) ok = false;
            if(ok) break;
            else cur--;
        }
        rEnd[j] = cur;
        cur--;
        //cout <<"    j = " << j << " rend = " << rEnd[j] << endl;
     }

    FOR(i, 0, n-1) FOR(j, 0, k-1) {
        dp[i][j] = (j > 0 || i-c[j] < 0 || possWhite(0, i-c[j], s)) && (j < k-1 || i+1 > n-1 || possWhite(i+1, n-1, s)) &&
                   possBlack(i-c[j]+1, i, s) && (j == 0 || possWhite(i-c[j], i-c[j], s)) && isDp(i - c[j] - 1, j-1) && endsAft (i+2, j+1, k, n);
        if (dp[i][j]) {
            fr[j] = i - c[j] + 1;
            if (to[j] == n) to[j] = i;
        }
        //cout << "  i= " << i << " j =" << j << "  dp[i][j] = " << dp[i][j] << endl;
    }

   // FOR(i, 0, k-1) cout << " i = " << i << "  fr = " << fr[i] << " to = " << to[i] << endl;

    FOR(i, 0, k-1) FOR(j, fr[i], to[i]) ret[j] = 'X';

    FOR(i, 0, n-1) canWh[i] = true;

    FOR(i, 0, n-1) FOR(j, 0, k-1) {
        if (dp[i][j]) {
            FOR(x, i - c[j]+1, i)
                canWh[x] = false;
        }
    }

    FOR(i, 0, n-1) if (canWh[i]) ret[i] = '_';

    FOR(i, 0, n-1) if (ret[i] == '.') ret[i] = '?';

    return ret;
}

• 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