Submission #362093

#	Time	Username	Problem	Language	Result	Execution time	Memory
362093		vishesh312	Paint By Numbers (IOI16_paint)	C++17	10 / 100	153 ms	492 KiB

paint

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

int invert_bits(int num) {
    int x = log2(num) + 1;
    for (int i = 0; i < x; ++i) {
       num = (num ^ (1 << i));
    }
    return num;
}

bool is_valid(string test, string s, vector<int> c) {
    int str = 0, fin = 0, i = 0;
    int k = c.size(), n = s.size();
    while (str < n and fin < n and i < k) {
        while (fin < n and test[str] == test[fin]) {
            ++fin;
        }
        if (test[str] == '1') {
            if ((fin - str) == c[i]) ++i;
            else return false;
        }
        str = fin;
    }
    return (i == k);
}

string solve_puzzle(string s, vector<int> c) {
    int n = s.size(), k = c.size();
    reverse(c.begin(), c.end());
    vector<int> results;
    //1 is white, 0 is black
    for (int i = 0; i < (1<<n); ++i) {
        bitset<20> b(i);
        string col = b.to_string();
        reverse(col.begin(), col.end());
        if ((int)b.count() == accumulate(c.begin(), c.end(), 0) and is_valid(col, s, c)) {
            results.push_back(i);
        }
    }
    vector<int> white_results;
    for (int xa : results) {
        bitset<20> b(xa);
        string x = b.to_string();
        string y = "";
        reverse(x.begin(), x.end());
        for (int i = 0; i < n; ++i) {
            if (x[i] == '1') y += '0';
            else y += '1';
        }
        int num = 0;
        for (int i = 0; i < n; ++i) {
            if (y[i] == '1') {
                num += (1<<i);
            }
        }
        white_results.push_back(num);
    }
    int b = results[0], w = white_results[0];
    for (auto x : results) b &= x;
    for (auto x : white_results) w &= x;
    string ret = "";
    for (int i = 0; i < n; ++i) {
        if ((1<<i)&w) ret += '_';
        else if ((1<<i)&b) ret += 'X';
        else ret += '?';
    }
    reverse(ret.begin(), ret.end());
    return ret;
}
/*
int main() {
    string s;
    cin >> s;
    int n;
    cin >> n;
    vector<int> v;
    while (n--) {
        int a;
        cin >> a;
        v.push_back(a);
    }
    cout << solve_puzzle(s, v);
}*/

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:29:23: warning: unused variable 'k' [-Wunused-variable]
   29 |     int n = s.size(), k = c.size();
      |                       ^

• 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