Submission #20613

#	Time	Username	Problem	Language	Result	Execution time	Memory
20613		model_code	Paint By Numbers (IOI16_paint)	C++11	100 / 100	436 ms	260680 KiB

paint

// name = paint_iz.cpp, type = cpp.g++11

#include "paint.h"
#include <iostream>
#include <cstdlib>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>

using namespace std;

//std::string solve_puzzle(int n, std::vector<int> C, std::vector<int> B, std::vector<int> W) {
std::string solve_puzzle(std::string S, std::vector<int> C) {
    int n = S.length();
    vector<int> B, W;
    for (int i = 0; i < n; i++) {
        if (S[i] == 'X') {
            B.push_back(i);
        }
        if (S[i] == '_') {
            W.push_back(i);
        }
    }
    n += 2;
    for (int i = 0; i < (int)B.size(); i++) B[i]++;
    for (int i = 0; i < (int)W.size(); i++) W[i]++;
   
    int k = C.size();
    vector<char> ans(n, 0);
    vector<vector<vector<int> > > dp(2, vector<vector<int> >(n, vector<int>(k + 1, 0)));
    vector<int> sumB(n), sumW(n);
    for (int it = 0; it < 3; it++) {
        sumB.assign(n, 0);
        sumW.assign(n, 0);
        for (int x : B) sumB[x]++;
        for (int x : W) sumW[x]++;
        for (int i = 1; i < n; i++) {
            sumB[i] += sumB[i - 1];
            sumW[i] += sumW[i - 1];
        }
        if (it == 2) break;

        dp[it][0][0] = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[it][i][j] |= dp[it][i - 1][j] && (sumB[i] - sumB[i - 1] == 0);
                dp[it][i][j] |= j > 0 && i > C[j - 1] && sumW[i - 1] - sumW[i - C[j - 1] - 1] == 0 && sumB[i] - sumB[i - 1] == 0 && dp[it][i - C[j - 1] - 1][j - 1];
            }
        }

        reverse(C.begin(), C.end());
        reverse(B.begin(), B.end());
        reverse(W.begin(), W.end());
        for (int i = 0; i < (int)B.size(); i++) B[i] = n - B[i] - 1;
        for (int i = 0; i < (int)W.size(); i++) W[i] = n - W[i] - 1;
    }
    reverse(dp[1].begin(), dp[1].end());
    for (int i = 1; i < n - 1; i++) {
        for (int j = 0; j <= k; j++) {
            if (dp[0][i][j] && dp[1][i][k - j]) {
                ans[i - 1] |= 1;
            }
        }
    }
    vector<int> a(n);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= k; j++) {
            if (j > 0 && i > C[j - 1] && sumW[i - 1] - sumW[i - C[j - 1] - 1] == 0 && sumB[i] - sumB[i - 1] == 0 && dp[0][i - C[j - 1] - 1][j - 1] && dp[1][i][k - j]) {
                a[i - C[j - 1]]++;
                a[i]--;
            }
        }
    }
    for (int i = 1; i < n; i++) {
        a[i] += a[i - 1];
        if (a[i] > 0) {
            ans[i - 1] |= 2;
        }
    }
    string res = "";
    for (int i = 0; i < n - 2; i++) {
        if (ans[i] == 1) res += '_';
        else if (ans[i] == 2) res += 'X';
        else if (ans[i] == 3) res += '?';
        else assert(0);
    }
    return res;
}

• 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