제출 #1284143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284143		gustavo_d	Paint By Numbers (IOI16_paint)	C++20	32 / 100	2 ms	352 KiB

paint

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


const int MAXN = 100;

string s; vector<int> c;
int n;

string solve_puzzle(string S, vector<int> C) {
    s = S; c = C;
    n = (int)s.size();

    int needed = -1;
    for (int val : c) needed += 1 + val;
    if (needed == n) {
        string ans;
        for (int g=0; g<(int)c.size(); g++) {
            for (int i=0; i<c[g]; i++) ans += 'X';
            ans += '_';
        }
        ans.pop_back();
        return ans;
    }

    string ans;
    for (int i=0; i<n; i++) {
        int bef = i; int G = -1; int x = -1;
        for (int g=0; g<(int)c.size(); g++) {
            if (x + 1 + c[g] <= bef) {
                G = g;
                x += 1 + c[g];
            } else break;
        }

        int after = n - i - 1;
        int need = 0;
        for (int g=G+1; g<(int)c.size(); g++) {
            need += c[g] + (g != G + 1);
        }
        ans += (after >= need ? '?' : 'X');
    }
    
    return ans;
}



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

// // TODO: define sz()

// const int MAXN = 100;

// bool dpPref[MAXN][MAXN+1][MAXN+1];
// bool dpInvSuf[MAXN][MAXN+1][MAXN+1];
// bool dp[MAXN][MAXN+1][MAXN+1];

// void solve(int n, string s, vector<int> c) {
//     for (int i=0; i<n; i++) {
//         for (int j=0; j<(int)c.size(); j++)
//             for (int k=0; k<=c[j]; k++)
//                 dp[i][j][k] = false;
//         dp[i][(int)c.size()][0] = false;
//     }

//     dp[0][0][0] = (s[0] != 'X');
//     dp[0][0][1] = (s[0] != '_');
//     for (int i=1; i<n; i++) {
//         // cout << i << ':';
//         for (int j=0; j<=(int)c.size(); j++) {
//             // branco
//             if (s[i] == '_' or s[i] == '.') {
//                 if (dp[i-1][j][0] or (j > 0 and dp[i-1][j-1][c[j-1]])) {
//                     dp[i][j][0] = true;
//                 }
//             }
//             if (j == (int)c.size()) continue;
//             // preto
//             for (int k=1; k<=c[j]; k++) {
//                 if (s[i] == '_') continue;
//                 if (dp[i-1][j][k-1]) dp[i][j][k] = true;
//             }
//         }
//     }
// }

// string solve_puzzle(string s, vector<int> c) {
//     int n = (int)s.size();
//     solve(n, s, c);
//     cout << endl << endl;
//     swap(dp, dpPref);
//     reverse(s.begin(), s.end());
//     reverse(c.begin(), c.end());
//     solve(n, s, c);
//     swap(dp, dpInvSuf);

//     string ans;
//     for (int i=0; i<n; i++) {
//         // cout << ans << '\n';
//         if (s[i] == '_' or s[i] == 'X') {
//             ans += s[i];
//             continue;
//         }

//         bool white = false;
//         for (int g=0; g<=(int)c.size(); g++) {
//             if (!dpPref[i][g][0]) continue;
//             if (!dpInvSuf[n-1-i][(int)c.size() - g][0]) continue;
//             white = true;
//         }

//         bool black = false;
//         for (int g=0; g<(int)c.size(); g++) {
//             for (int j=1; j<=c[g]; j++) {
//                 if (!dpPref[i][g][j]) continue;
//                 if (!dpInvSuf[n-1-i][(int)c.size() - g][c[j] - j + 1]) continue;
//                 black = true;
//             }
//         }
//         // for (int g=-1; g<(int)c.size(); g++) {
//         //     if (g == -1) {
//         //         bool can = true;
//         //         for (int j=0; j<i; j++) {
//         //             if (s[j] == 'X') can = false;
//         //         }
//         //         if (!can) continue;
//         //     } else {
//         //         bool can = false;
//         //         for (int j=i-1; j>=0; j--) {
//         //             if (s[j] == 'X') break;
//         //             if (dp[j][g][c[g]]) can = true;
//         //         }
//         //         if (!can) continue;
//         //     }

//         //     if (g == (int)c.size() - 1) {
//         //         bool can = true;
//         //         for (int j=i+1; j<n; j++) {
//         //             if (s[j] == '_') can = false;
//         //         }
//         //         if (!can) continue;
//         //     } else {
//         //         bool can = false;
//         //         for (int j=i+1; j<n; j++) {
//         //             if (dpInvSuf[n-1-j][g+1][0]) can = true;
//         //         }
//         //         if (!can) continue;
//         //     }
//         //     white = true;
//         // }
//         cout << white << ' ' << black << '\n';

//         if (black and white) {
//             ans += '?';
//             continue;
//         }
//         if (white) ans += '_';
//         if (black) ans += 'X';
//     }

//     return ans;
// }

컴파일 시 표준 에러 (stderr) 메시지

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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