oj.uz

Submission #362093

# Submission time Handle Problem Language Result Execution time Memory
362093 2021-02-01T17:41:45 Z vishesh312 Paint By Numbers (IOI16_paint) C++17
10 / 100
 153 ms 492 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB n = 13, m = 1
2 Correct 35 ms 364 KB n = 18, m = 1
3 Correct 15 ms 364 KB n = 17, m = 1
4 Correct 1 ms 364 KB n = 1, m = 1
5 Correct 121 ms 364 KB n = 20, m = 1
6 Correct 139 ms 364 KB n = 20, m = 1
7 Correct 115 ms 380 KB n = 20, m = 1

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB n = 13, m = 1
2 Correct 35 ms 364 KB n = 18, m = 1
3 Correct 15 ms 364 KB n = 17, m = 1
4 Correct 1 ms 364 KB n = 1, m = 1
5 Correct 121 ms 364 KB n = 20, m = 1
6 Correct 139 ms 364 KB n = 20, m = 1
7 Correct 115 ms 380 KB n = 20, m = 1
8 Correct 119 ms 492 KB n = 20, m = 5
9 Correct 27 ms 364 KB n = 18, m = 3
10 Correct 18 ms 364 KB n = 17, m = 2
11 Correct 137 ms 380 KB n = 20, m = 2
12 Correct 14 ms 364 KB n = 17, m = 4
13 Correct 17 ms 364 KB n = 17, m = 6
14 Correct 14 ms 364 KB n = 17, m = 1
15 Correct 14 ms 364 KB n = 17, m = 4
16 Correct 1 ms 364 KB n = 13, m = 3
17 Correct 28 ms 364 KB n = 18, m = 4
18 Correct 153 ms 492 KB n = 20, m = 10
19 Correct 71 ms 364 KB n = 19, m = 10

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB n = 13, m = 1
2 Correct 35 ms 364 KB n = 18, m = 1
3 Correct 15 ms 364 KB n = 17, m = 1
4 Correct 1 ms 364 KB n = 1, m = 1
5 Correct 121 ms 364 KB n = 20, m = 1
6 Correct 139 ms 364 KB n = 20, m = 1
7 Correct 115 ms 380 KB n = 20, m = 1
8 Correct 119 ms 492 KB n = 20, m = 5
9 Correct 27 ms 364 KB n = 18, m = 3
10 Correct 18 ms 364 KB n = 17, m = 2
11 Correct 137 ms 380 KB n = 20, m = 2
12 Correct 14 ms 364 KB n = 17, m = 4
13 Correct 17 ms 364 KB n = 17, m = 6
14 Correct 14 ms 364 KB n = 17, m = 1
15 Correct 14 ms 364 KB n = 17, m = 4
16 Correct 1 ms 364 KB n = 13, m = 3
17 Correct 28 ms 364 KB n = 18, m = 4
18 Correct 153 ms 492 KB n = 20, m = 10
19 Correct 71 ms 364 KB n = 19, m = 10
20 Runtime error 1 ms 492 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB n = 13, m = 1
2 Correct 35 ms 364 KB n = 18, m = 1
3 Correct 15 ms 364 KB n = 17, m = 1
4 Correct 1 ms 364 KB n = 1, m = 1
5 Correct 121 ms 364 KB n = 20, m = 1
6 Correct 139 ms 364 KB n = 20, m = 1
7 Correct 115 ms 380 KB n = 20, m = 1
8 Correct 119 ms 492 KB n = 20, m = 5
9 Correct 27 ms 364 KB n = 18, m = 3
10 Correct 18 ms 364 KB n = 17, m = 2
11 Correct 137 ms 380 KB n = 20, m = 2
12 Correct 14 ms 364 KB n = 17, m = 4
13 Correct 17 ms 364 KB n = 17, m = 6
14 Correct 14 ms 364 KB n = 17, m = 1
15 Correct 14 ms 364 KB n = 17, m = 4
16 Correct 1 ms 364 KB n = 13, m = 3
17 Correct 28 ms 364 KB n = 18, m = 4
18 Correct 153 ms 492 KB n = 20, m = 10
19 Correct 71 ms 364 KB n = 19, m = 10
20 Runtime error 1 ms 492 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB n = 13, m = 1
2 Correct 35 ms 364 KB n = 18, m = 1
3 Correct 15 ms 364 KB n = 17, m = 1
4 Correct 1 ms 364 KB n = 1, m = 1
5 Correct 121 ms 364 KB n = 20, m = 1
6 Correct 139 ms 364 KB n = 20, m = 1
7 Correct 115 ms 380 KB n = 20, m = 1
8 Correct 119 ms 492 KB n = 20, m = 5
9 Correct 27 ms 364 KB n = 18, m = 3
10 Correct 18 ms 364 KB n = 17, m = 2
11 Correct 137 ms 380 KB n = 20, m = 2
12 Correct 14 ms 364 KB n = 17, m = 4
13 Correct 17 ms 364 KB n = 17, m = 6
14 Correct 14 ms 364 KB n = 17, m = 1
15 Correct 14 ms 364 KB n = 17, m = 4
16 Correct 1 ms 364 KB n = 13, m = 3
17 Correct 28 ms 364 KB n = 18, m = 4
18 Correct 153 ms 492 KB n = 20, m = 10
19 Correct 71 ms 364 KB n = 19, m = 10
20 Runtime error 1 ms 492 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB n = 13, m = 1
2 Correct 35 ms 364 KB n = 18, m = 1
3 Correct 15 ms 364 KB n = 17, m = 1
4 Correct 1 ms 364 KB n = 1, m = 1
5 Correct 121 ms 364 KB n = 20, m = 1
6 Correct 139 ms 364 KB n = 20, m = 1
7 Correct 115 ms 380 KB n = 20, m = 1
8 Correct 119 ms 492 KB n = 20, m = 5
9 Correct 27 ms 364 KB n = 18, m = 3
10 Correct 18 ms 364 KB n = 17, m = 2
11 Correct 137 ms 380 KB n = 20, m = 2
12 Correct 14 ms 364 KB n = 17, m = 4
13 Correct 17 ms 364 KB n = 17, m = 6
14 Correct 14 ms 364 KB n = 17, m = 1
15 Correct 14 ms 364 KB n = 17, m = 4
16 Correct 1 ms 364 KB n = 13, m = 3
17 Correct 28 ms 364 KB n = 18, m = 4
18 Correct 153 ms 492 KB n = 20, m = 10
19 Correct 71 ms 364 KB n = 19, m = 10
20 Runtime error 1 ms 492 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB n = 13, m = 1
2 Correct 35 ms 364 KB n = 18, m = 1
3 Correct 15 ms 364 KB n = 17, m = 1
4 Correct 1 ms 364 KB n = 1, m = 1
5 Correct 121 ms 364 KB n = 20, m = 1
6 Correct 139 ms 364 KB n = 20, m = 1
7 Correct 115 ms 380 KB n = 20, m = 1
8 Correct 119 ms 492 KB n = 20, m = 5
9 Correct 27 ms 364 KB n = 18, m = 3
10 Correct 18 ms 364 KB n = 17, m = 2
11 Correct 137 ms 380 KB n = 20, m = 2
12 Correct 14 ms 364 KB n = 17, m = 4
13 Correct 17 ms 364 KB n = 17, m = 6
14 Correct 14 ms 364 KB n = 17, m = 1
15 Correct 14 ms 364 KB n = 17, m = 4
16 Correct 1 ms 364 KB n = 13, m = 3
17 Correct 28 ms 364 KB n = 18, m = 4
18 Correct 153 ms 492 KB n = 20, m = 10
19 Correct 71 ms 364 KB n = 19, m = 10
20 Runtime error 1 ms 492 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -