제출 #591284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591284		Vanilla	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	320 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
const int maxn = 102;
vector <vector <int> > v[maxn];

// string solve_puzzle(string s, vector<int> c) {
//     int n = s.size();
//     int k = c.size();
//     string rs = s;
//     for (int i = 0; i + c[0] - 1 < n; i++){
//         bool good = 1;
//         for (int j = i; j < i + c[0] - 1; j++){
//             if (s[j] == '_') good = 0;
//         }
//         if (good) v[0].push_back(vector <int> (1, i + c[0] - 1));
//     }
//     for (int i = 1; i < k; i++){
//         for (auto &vc: v[i-1]){
//             int idx = vc.back();
//             for (int j = idx + 2; j + c[i] - 1 < n; j++) {
//                 bool good = 1;
//                 for (int k = j; k < j + c[i] - 1; k++) {
//                     if (s[k] == '_') {
//                         good = 0;
//                         break;
//                     }
//                 }
//                 if (good) {
//                     vector <int> s = vc;
//                     s.push_back(j + 2 + c[i] - 1);
//                     v[i].push_back(s);
//                 }

//             }
//         }
//     }
//     for (auto &i: v[1]) {
//         for (int &j: i) {
//             cout << j << " ";
//         }
//         cout << "\n";
//     }
//     return "";
// }

// int dp[maxn][maxn][2]; // dp[i][j][k] -> (k == 0 ? min: max) position for the last X on the j-th partition considering first i partitions
int dp[maxn][maxn]; // dp[i][j] -> if you can finish i-th partition on the position j
int l[maxn];
int r[maxn];

string solve_puzzle(string s, vector<int> c) {
    int n = s.size();
    int k = c.size();
    string rs = s;
    for (int i = 0; i < k; i++) l[i] = 1e9, r[i] = -1;
    l[0] = c[0] - 1;
    for (int i = 1; i < k; i++){
        l[i] = l[i-1] + c[i] + 1;
    }
    r[k-1] = n-1;
    for (int i = k - 2; i >= 0; i--){
        r[i] = r[i + 1] - c[i + 1] - 1;
    }
    // for (int i = 0; i < k; i++){
    //     cout << i << " " << l[i] << " " << r[i] << "\n";
    // }
    for (int i = 0; i < k; i++){
        // cout << l[i] << " " << l[i] + c[i] - 1 << " " << r[i] - c[i] + 1 << " " << r[i] << "\n";
        for (int j = r[i] - c[i] + 1; j <= l[i]; j++) {
            rs[j] = 'X';
        }
    }
    for (int i = 0; i < n; i++){
        if (i - 1 >= 0 && i + 1 < n && rs[i-1] == 'X' && rs[i + 1] == 'X' && rs[i] == '.') rs[i] = '_';
        else if (rs[i] == '.') rs[i] = '?';
    }

    return rs;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10