제출 #428011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428011		Mazaalai	Paint By Numbers (IOI16_paint)	C++14	10 / 100	2088 ms	532 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
string s;
const int N = 5005;
const int K = 105;
vector <int> c(K), minNeedLen(K, 0);
vector <set <char> > chars(N);
string ans = "";
int n, k;
void solve(int idx, string&cur) {
    int pos = cur.size();
    if (pos > n+1) return;
    // cout << cur << '\n';
    if (pos == n+1) {
        if (idx <= k) return;
        // cout << cur << '\n';
        for (int i = 1; i <= n; i++) {
            chars[i].insert((cur[i] == 'X' ? 'X' : '_'));
        }
        return;
    }
    if (pos + minNeedLen[idx] - 1 > n || pos > n) {
        return;
    }
    if (idx == k+1 && pos < n+1) {
        int tmp = n+1 - pos;
        for (int i = 0; i < tmp; i++) {
            if (s[pos + i] == 'X') return;
        }
        for (int i = 0; i < tmp; i++) cur.push_back('_');
        solve(idx, cur);
        for (int i = 0; i < tmp; i++) cur.pop_back();
        return;
    }
    if (s[pos] != 'X') {
        cur.push_back('_');
        solve(idx, cur);
        cur.pop_back();
    }
    for (int i = pos; i < pos + c[idx]; i++) {
        if (s[i] == '_') {
            // cout << pos << ' ' << idx << ' ' << cur << '\n';
            return;
        }
    }
    int tmp = c[idx];
    for (int i = 0; i < tmp; i++) {
        cur.push_back('X');
    }
    if (idx != k)
    cur.push_back('_');
    solve(idx+1, cur);
    if (idx != k)
    cur.pop_back();
    for (int i = 0; i < tmp; i++) {
        cur.pop_back();
    }
}
string solve_puzzle(string s1, vector<int> c1) {
    n = s1.size(), k = c1.size();
    s = 'A' + s1 + 'A';
    for (int i = 1; i <= k; i++) c[i] = c1[i-1];
    for (int i = 0; i < n+2; i++) ans += '?';
    for (int i = k; i >= 1; i--) 
        minNeedLen[i] = c[i] + (i < k ? minNeedLen[i+1]+1 : 0);
    string cur = "A";
    solve(1, cur);
    for (int i = 1; i <= n; i++) {
        if (chars[i].size() != 1) ans[i] = '?';
        else ans[i] = *chars[i].begin();
    }
    ans = ans.substr(1, n);
    return ans;
}

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