Submission #1167893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167893		SmuggingSpun	Paint By Numbers (IOI16_paint)	C++20	80 / 100	2092 ms	472 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 && false){
        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;
    }
    if(s == string(n, '.') && false){
        string ans = "";
        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];
        };
        string ans = "";
        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;
    }
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:118:1: warning: control reaches end of non-void function [-Wreturn-type]
  118 | }
      | ^
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