Submission #1168209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168209		SmuggingSpun	Paint By Numbers (IOI16_paint)	C++20	80 / 100	215 ms	1096 KiB

paint

#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
string solve_puzzle(string s, vector<int>c) {
    int n = s.size();
    if(n <= 20){
        for(char& c : s){
            if(c != '.'){
                c = (c == 'X' ? '1' : '0');
            }
        }
        vector<int>ans(n, 0);
        for(int mask = (1 << n) - 1; mask > -1; mask--){
            string cur = "";
            vector<int>C;
            bool flag = true;
            for(int i = 0; i < n; i++){
                cur += char((mask >> i & 1) + 48);
                if(s[i] != '.' && cur.back() != s[i]){
                    flag = false;
                    break;
                }
            }
            if(flag){
                cur += '0';
                for(int i = 0, cnt = 0; i <= n; i++){
                    if(cur[i] == '0' && cnt > 0){
                        C.emplace_back(cnt);
                        cnt = 0;
                    }
                    else if(cur[i] == '1'){
                        cnt++;
                    }
                }
                if(C == c){ 
                    for(int i = 0; i < n; i++){
                        ans[i] |= 1 << (cur[i] - 48);
                    }
                }
            }
        }
        string ret = "";
        for(int i = 0; i < n; i++){
            ret += (ans[i] == 1 ? '_' : (ans[i] == 2 ? 'X' : '?'));
        }
        return ret;
    }
    string ans = "";
    if(s == string(n, '.')){
        for(int i = 0; i < n; i++){
            int p = -1, left = i, right;
            if(left >= c[0]){
                for(int j = 0; j < c.size(); left -= c[j++] + 1){
                    if(j + 1 == c.size() || left - c[j] <= c[j + 1]){
                        p = j;
                        break;
                    }
                }
            }
            if(accumulate(c.begin() + p + 1, c.end(), 0) + int(c.size()) - p - 1 > n - i){
                ans += 'X';
            }
            else{
                bool flag = false;
                for(int j = left = 0; !flag && j < c.size() && left <= i; j++, left++){
                    for(int k = 0; !flag && k < c[j] && left++ <= i; k++){
                        right = c[j] - k - 1;
                        for(int t = j + 1; t < c.size(); t++){
                            right += c[t] + 1;
                        }
                        if(right < n - i){
                            flag = true;
                        }
                    }
                }
                ans += (flag ? '?' : '_');
            }
        }
        return ans;
    }
    if(n <= 100){
        vector<bool>flag(2);
        auto work = [&] (bool id){
            vector<int>fbl(n);
            fbl[0] = int(s[0] == '_');
            for(int i = 1; i < n; i++){
                fbl[i] = fbl[i - 1] + int(s[i] == '_');
            }            
            vector<bool>dp(n + 2, false);
            dp[n] = true;
            for(int i = n - 1; i > -1 && s[i] != 'X'; i--){
                dp[i] = true;
            }
            for(int i = int(c.size()) - 1; i > -1; i--){
                vector<bool>ndp(n + 2, false);
                for(int j = n - c[i]; j > -1; j--){
                    ndp[j] = ((s[j] != 'X' && ndp[j + 1]) || (fbl[j + c[i] - 1] == (j == 0 ? 0 : fbl[j - 1]) && ((i + 1 == c.size() && dp[j + c[i]]) || (i + 1 < c.size() && j + c[i] < n && s[j + c[i]] != 'X' && dp[j + c[i] + 1]))));
                }                
                swap(dp, ndp);
            }
            flag[id] = dp[0];
        };
        for(int i = 0; i < n; i++){
            if(s[i] != '.'){
                ans += s[i];
                continue;
            }
            s[i] = 'X';
            work(false);
            s[i] = '_';            
            work(true);
            s[i] = '.';
            ans += (flag[0] && flag[1] ? '?' : (flag[0] ? 'X' : '_'));
        }
        return ans;
    }
    int k = c.size();
    c.insert(c.begin(), -1);
    s = '#' + s + '#';
    vector<vector<bool>>pref(n + 1, vector<bool>(k + 1, false)), suf(n + 2, vector<bool>(k + 2, false));
    vector<int>lbl(n + 1), rbl(n + 2);
    pref[lbl[0] = 0][0] = suf[rbl[n + 1] = n + 1][k + 1] = true;
    for(int i = 1; i <= n; i++){
        pref[i][0] = (pref[i - 1][0] && s[i] != 'X');
        pref[i][1] = (((i - c[1] >= (lbl[i] = (s[i] == '_' ? i : lbl[i - 1]))) && pref[i - c[1]][0]) || (s[i] != 'X' && pref[i - 1][1]));
        for(int j = 2; j <= k; j++){
            pref[i][j] = ((pref[i - 1][j] && s[i] != 'X') || (i - c[j] >= max(1, lbl[i]) && s[i - c[j]] != 'X' && pref[i - c[j] - 1][j - 1] && s[i] != '_'));
        }
    }
    for(int i = n; i > 0; i--){
        suf[i][k + 1] = (suf[i + 1][k + 1] && s[i] != 'X');
        suf[i][k] = ((i + c[k] <= (rbl[i] = (s[i] == '_' ? i : rbl[i + 1])) && suf[i + c[k]][k + 1]) || (s[i] != 'X' && suf[i + 1][k]));
        for(int j = k - 1; j > 0; j--){
            suf[i][j] = ((suf[i + 1][j] && s[i] != 'X') || (i + c[j] <= min(n, rbl[i]) && s[ i + c[j]] != 'X' && suf[i + c[j] + 1][j + 1] && s[i] != '_'));
        }
    }
    vector<int>fx(n + 2, 0);
    for(int i = 1; i <= n; i++){
        if(s[i] == '.'){
            for(int j = 1; j <= k; j++){
                int left = i - c[j] - int(j > 1);
                if(i - c[j] >= lbl[i] && left > -1 && s[left + int(j > 1)] != 'X' && pref[left][j - 1] && s[i + 1] != 'X' && i + 1 + int(j < k) < n + 2 && suf[i + 1 + (j < k)][j + 1]){
                    fx[i - c[j] + 1]++;
                    fx[i + 1]--;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        fx[i] += fx[i - 1];
        if(s[i] != '.'){
            ans += s[i];
            continue;
        }
        if(fx[i] == 0){
            ans += '_';
        }
        else{
            bool flag = false;
            for(int j = 0; j <= k; j++){
                if(pref[i - 1][j] && suf[i + 1][j + 1]){
                    flag = true;
                    break;
                }
            }
            ans += (flag ? '?' : 'X');
        }
    }
    return ans;
}

Compilation message (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: 27 / 27
• Subtask 5: 21 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10