Submission #691434

#	Time	Username	Problem	Language	Result	Execution time	Memory
691434		zeroesandones	Paint By Numbers (IOI16_paint)	C++17	10 / 100	458 ms	420 KiB

paint

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

using ll = long long;
using pi = pair<long long, long long>;
using vi = vector<long long>;

#define pb emplace_back

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

    vector<vi> sets;
    string res(n, '?');
    for(int i = 0; i < (1<<n); ++i) {
        vi subset;
        for(int j = 0; j < n; ++j) {
            if(i & (1<<j))
                subset.pb(1);
            else
                subset.pb(0);
        }

        vi len;
        ll curr = 0;
        for(int j = 0; j < n; ++j) {
            if(subset[j] == 0) {
                if(curr != 0)
                    len.pb(curr);
                curr = 0;
            } else {
                ++curr;
            }
        }
        if(curr != 0) len.pb(curr);
        if((int) len.size() != k) continue;
        bool valid = true;
        for(int j = 0; j < k; ++j) {
            if(len[j] != c[j]) {
                valid = false;
                break;
            }
        }

        if(valid)
            sets.pb(subset);
    }

    for(int i = 0; i < n; ++i) {
        int fr = sets[0][i];
        bool confuse = false;
        for(int j = 1; j < (int) sets.size(); ++j) {
            if(sets[j][i] != fr) {
                confuse = true;
                break;
            }
        }
        if(!confuse)
            res[i] = (fr ? 'X' : '_');
    }

    return res;
}

• 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