Submission #1167831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167831		SmuggingSpun	Paint By Numbers (IOI16_paint)	C++20	32 / 100	229 ms	420 KiB

paint

#include<bits/stdc++.h>
#include "paint.h"
using namespace std;
string solve_puzzle(string s, vector<int>c) {
    for(char& c : s){
        if(c != '.'){
            c = (c == 'X' ? '1' : '0');
        }
    }
    int n = s.size();
    if(n <= 20){
        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, '.')){
        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;
    }
}

Compilation message (stderr)

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