oj.uz

답안 #902615

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
902615 2024-01-10T20:34:35 Z Blagoj Paint By Numbers (IOI16_paint) C++17
32 / 100
 1 ms 1884 KB 
#include <bits/stdc++.h>
#include "paint.h"

using namespace std;

const int mxn = 2e5 + 10;

int pfxW[mxn], pfxB[mxn];

int getW(int l, int r) {
    return pfxW[r] - pfxW[l - 1];
}

int getB(int l, int n) {
    return pfxB[n - 1] - pfxB[l - 1];
}

string solve(string s, vector<int> c) {
    memset(pfxW, 0, sizeof(pfxW));
    memset(pfxB, 0, sizeof(pfxB));
    s = "." + s;
    int n = s.size(), k = c.size();
    for (int i = 1; i < n; i++) pfxW[i] = pfxW[i - 1] + (s[i] == '_');
    for (int i = 1; i < n; i++) pfxB[i] = pfxB[i - 1] + (s[i] == 'X');
    bool dp[n][k + 1];
    int from[n][k + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    int pos = n;
    for (int i = 1; i < n; i++) {
        if (s[i] != 'X') dp[i][0] = dp[i - 1][0];
        for (int j = 1; j <= k; j++) {
            if (((j == 1 && i - c[j - 1] >= 0) || (j > 1 && i - c[j - 1] - 1 >= 0)) && getW(i - c[j - 1] + 1, i) == 0) {
                if (j < k) {
                    int val = (j == 1 ? dp[i - c[j - 1]][j - 1] : dp[i - c[j - 1] - 1][j - 1]);
                    if (val) {
                        dp[i][j] = 1;
                        from[i][j] = i - c[j - 1] - 1;
                    }
                }
                else if (getB(i + 1, n) == 0) {
                    int val = (j == 1 ? dp[i - c[j - 1]][j - 1] : dp[i - c[j - 1] - 1][j - 1]);
                    if (val) {
                        dp[i][j] = 1;
                        from[i][j] = i - c[j - 1] - 1;
                        pos = min(pos, i);
                    }
                }
            }
        }
    }
    string ans;
    for (int i = 0; i < n; i++) ans += "_";
    int cnt = k;
    while (pos && cnt) {
        if (dp[pos][cnt]) {
            for (int i = pos; i > from[pos][cnt] + 1; i--) ans[i] = 'X';
            pos = from[pos][cnt];
            cnt--;
        }
        else pos--;
    }
    return ans.substr(1);
}

string solve_puzzle(string s, vector<int> c) {
    string l = solve(s, c);
    reverse(s.begin(), s.end());
    reverse(c.begin(), c.end());
    string r = solve(s, c);
    reverse(r.begin(), r.end());
    if (l == r) return l;
    reverse(s.begin(), s.end());
    string ans = "";
    for (int i = 0; i < s.size(); i++) ans += "?";
    int cntL = 0, cntR = 0;
    for (int i = 0; i < s.size(); i++) {
        if (l[i] != '_' || r[i] != '_') break;
        ans[i] = '_';
    }
    for (int i = s.size() - 1; i >= 0; i--) {
        if (l[i] != '_' || r[i] != '_') break;
        ans[i] = '_';
    }
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '_') ans[i] = '_';
        if (l[i] == 'X' && r[i] == 'X' && cntL == cntR) ans[i] = 'X';
        if (i && l[i] == '_' && l[i - 1] == 'X') cntL++;
        if (i && r[i] == '_' && r[i - 1] == 'X') cntR++;
    } 
    int cntEmpty = 0;
    int smallest = c[0];
    for (int i = 1; i < c.size(); i++) smallest = min(smallest, c[i]);
    return ans;
}

Compilation message

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i = 0; i < s.size(); i++) ans += "?";
      |                     ~~^~~~~~~~~~
paint.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
paint.cpp:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
paint.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = 1; i < c.size(); i++) smallest = min(smallest, c[i]);
      |                     ~~^~~~~~~~~~
paint.cpp:91:9: warning: unused variable 'cntEmpty' [-Wunused-variable]
   91 |     int cntEmpty = 0;
      |         ^~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1880 KB n = 13, m = 1
2 Correct 1 ms 1880 KB n = 18, m = 1
3 Correct 1 ms 1884 KB n = 17, m = 1
4 Correct 1 ms 1884 KB n = 1, m = 1
5 Correct 1 ms 1880 KB n = 20, m = 1
6 Correct 1 ms 1884 KB n = 20, m = 1
7 Correct 1 ms 1884 KB n = 20, m = 1

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1880 KB n = 13, m = 1
2 Correct 1 ms 1880 KB n = 18, m = 1
3 Correct 1 ms 1884 KB n = 17, m = 1
4 Correct 1 ms 1884 KB n = 1, m = 1
5 Correct 1 ms 1880 KB n = 20, m = 1
6 Correct 1 ms 1884 KB n = 20, m = 1
7 Correct 1 ms 1884 KB n = 20, m = 1
8 Correct 1 ms 1880 KB n = 20, m = 5
9 Correct 1 ms 1880 KB n = 18, m = 3
10 Correct 1 ms 1884 KB n = 17, m = 2
11 Correct 1 ms 1884 KB n = 20, m = 2
12 Correct 1 ms 1884 KB n = 17, m = 4
13 Correct 1 ms 1884 KB n = 17, m = 6
14 Correct 1 ms 1880 KB n = 17, m = 1
15 Correct 1 ms 1884 KB n = 17, m = 4
16 Correct 1 ms 1884 KB n = 13, m = 3
17 Correct 1 ms 1884 KB n = 18, m = 4
18 Correct 1 ms 1884 KB n = 20, m = 10
19 Correct 1 ms 1884 KB n = 19, m = 10

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1880 KB n = 13, m = 1
2 Correct 1 ms 1880 KB n = 18, m = 1
3 Correct 1 ms 1884 KB n = 17, m = 1
4 Correct 1 ms 1884 KB n = 1, m = 1
5 Correct 1 ms 1880 KB n = 20, m = 1
6 Correct 1 ms 1884 KB n = 20, m = 1
7 Correct 1 ms 1884 KB n = 20, m = 1
8 Correct 1 ms 1880 KB n = 20, m = 5
9 Correct 1 ms 1880 KB n = 18, m = 3
10 Correct 1 ms 1884 KB n = 17, m = 2
11 Correct 1 ms 1884 KB n = 20, m = 2
12 Correct 1 ms 1884 KB n = 17, m = 4
13 Correct 1 ms 1884 KB n = 17, m = 6
14 Correct 1 ms 1880 KB n = 17, m = 1
15 Correct 1 ms 1884 KB n = 17, m = 4
16 Correct 1 ms 1884 KB n = 13, m = 3
17 Correct 1 ms 1884 KB n = 18, m = 4
18 Correct 1 ms 1884 KB n = 20, m = 10
19 Correct 1 ms 1884 KB n = 19, m = 10
20 Correct 1 ms 1884 KB n = 100, m = 5
21 Correct 1 ms 1880 KB n = 90, m = 3
22 Correct 1 ms 1884 KB n = 86, m = 2
23 Correct 1 ms 1884 KB n = 81, m = 4
24 Correct 1 ms 1880 KB n = 89, m = 10
25 Correct 1 ms 1884 KB n = 81, m = 23
26 Correct 1 ms 1884 KB n = 86, m = 8
27 Correct 1 ms 1884 KB n = 53, m = 22
28 Correct 1 ms 1884 KB n = 89, m = 35
29 Correct 1 ms 1884 KB n = 63, m = 25
30 Correct 1 ms 1884 KB n = 100, m = 50
31 Correct 1 ms 1880 KB n = 99, m = 50

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1880 KB n = 13, m = 1
2 Correct 1 ms 1880 KB n = 18, m = 1
3 Correct 1 ms 1884 KB n = 17, m = 1
4 Correct 1 ms 1884 KB n = 1, m = 1
5 Correct 1 ms 1880 KB n = 20, m = 1
6 Correct 1 ms 1884 KB n = 20, m = 1
7 Correct 1 ms 1884 KB n = 20, m = 1
8 Correct 1 ms 1880 KB n = 20, m = 5
9 Correct 1 ms 1880 KB n = 18, m = 3
10 Correct 1 ms 1884 KB n = 17, m = 2
11 Correct 1 ms 1884 KB n = 20, m = 2
12 Correct 1 ms 1884 KB n = 17, m = 4
13 Correct 1 ms 1884 KB n = 17, m = 6
14 Correct 1 ms 1880 KB n = 17, m = 1
15 Correct 1 ms 1884 KB n = 17, m = 4
16 Correct 1 ms 1884 KB n = 13, m = 3
17 Correct 1 ms 1884 KB n = 18, m = 4
18 Correct 1 ms 1884 KB n = 20, m = 10
19 Correct 1 ms 1884 KB n = 19, m = 10
20 Correct 1 ms 1884 KB n = 100, m = 5
21 Correct 1 ms 1880 KB n = 90, m = 3
22 Correct 1 ms 1884 KB n = 86, m = 2
23 Correct 1 ms 1884 KB n = 81, m = 4
24 Correct 1 ms 1880 KB n = 89, m = 10
25 Correct 1 ms 1884 KB n = 81, m = 23
26 Correct 1 ms 1884 KB n = 86, m = 8
27 Correct 1 ms 1884 KB n = 53, m = 22
28 Correct 1 ms 1884 KB n = 89, m = 35
29 Correct 1 ms 1884 KB n = 63, m = 25
30 Correct 1 ms 1884 KB n = 100, m = 50
31 Correct 1 ms 1880 KB n = 99, m = 50
32 Incorrect 1 ms 1884 KB char #0 differ - expected: '?', found: '_'
33 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1880 KB n = 13, m = 1
2 Correct 1 ms 1880 KB n = 18, m = 1
3 Correct 1 ms 1884 KB n = 17, m = 1
4 Correct 1 ms 1884 KB n = 1, m = 1
5 Correct 1 ms 1880 KB n = 20, m = 1
6 Correct 1 ms 1884 KB n = 20, m = 1
7 Correct 1 ms 1884 KB n = 20, m = 1
8 Correct 1 ms 1880 KB n = 20, m = 5
9 Correct 1 ms 1880 KB n = 18, m = 3
10 Correct 1 ms 1884 KB n = 17, m = 2
11 Correct 1 ms 1884 KB n = 20, m = 2
12 Correct 1 ms 1884 KB n = 17, m = 4
13 Correct 1 ms 1884 KB n = 17, m = 6
14 Correct 1 ms 1880 KB n = 17, m = 1
15 Correct 1 ms 1884 KB n = 17, m = 4
16 Correct 1 ms 1884 KB n = 13, m = 3
17 Correct 1 ms 1884 KB n = 18, m = 4
18 Correct 1 ms 1884 KB n = 20, m = 10
19 Correct 1 ms 1884 KB n = 19, m = 10
20 Correct 1 ms 1884 KB n = 100, m = 5
21 Correct 1 ms 1880 KB n = 90, m = 3
22 Correct 1 ms 1884 KB n = 86, m = 2
23 Correct 1 ms 1884 KB n = 81, m = 4
24 Correct 1 ms 1880 KB n = 89, m = 10
25 Correct 1 ms 1884 KB n = 81, m = 23
26 Correct 1 ms 1884 KB n = 86, m = 8
27 Correct 1 ms 1884 KB n = 53, m = 22
28 Correct 1 ms 1884 KB n = 89, m = 35
29 Correct 1 ms 1884 KB n = 63, m = 25
30 Correct 1 ms 1884 KB n = 100, m = 50
31 Correct 1 ms 1880 KB n = 99, m = 50
32 Incorrect 1 ms 1884 KB char #0 differ - expected: '?', found: '_'
33 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1880 KB n = 13, m = 1
2 Correct 1 ms 1880 KB n = 18, m = 1
3 Correct 1 ms 1884 KB n = 17, m = 1
4 Correct 1 ms 1884 KB n = 1, m = 1
5 Correct 1 ms 1880 KB n = 20, m = 1
6 Correct 1 ms 1884 KB n = 20, m = 1
7 Correct 1 ms 1884 KB n = 20, m = 1
8 Correct 1 ms 1880 KB n = 20, m = 5
9 Correct 1 ms 1880 KB n = 18, m = 3
10 Correct 1 ms 1884 KB n = 17, m = 2
11 Correct 1 ms 1884 KB n = 20, m = 2
12 Correct 1 ms 1884 KB n = 17, m = 4
13 Correct 1 ms 1884 KB n = 17, m = 6
14 Correct 1 ms 1880 KB n = 17, m = 1
15 Correct 1 ms 1884 KB n = 17, m = 4
16 Correct 1 ms 1884 KB n = 13, m = 3
17 Correct 1 ms 1884 KB n = 18, m = 4
18 Correct 1 ms 1884 KB n = 20, m = 10
19 Correct 1 ms 1884 KB n = 19, m = 10
20 Correct 1 ms 1884 KB n = 100, m = 5
21 Correct 1 ms 1880 KB n = 90, m = 3
22 Correct 1 ms 1884 KB n = 86, m = 2
23 Correct 1 ms 1884 KB n = 81, m = 4
24 Correct 1 ms 1880 KB n = 89, m = 10
25 Correct 1 ms 1884 KB n = 81, m = 23
26 Correct 1 ms 1884 KB n = 86, m = 8
27 Correct 1 ms 1884 KB n = 53, m = 22
28 Correct 1 ms 1884 KB n = 89, m = 35
29 Correct 1 ms 1884 KB n = 63, m = 25
30 Correct 1 ms 1884 KB n = 100, m = 50
31 Correct 1 ms 1880 KB n = 99, m = 50
32 Incorrect 1 ms 1884 KB char #0 differ - expected: '?', found: '_'
33 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1880 KB n = 13, m = 1
2 Correct 1 ms 1880 KB n = 18, m = 1
3 Correct 1 ms 1884 KB n = 17, m = 1
4 Correct 1 ms 1884 KB n = 1, m = 1
5 Correct 1 ms 1880 KB n = 20, m = 1
6 Correct 1 ms 1884 KB n = 20, m = 1
7 Correct 1 ms 1884 KB n = 20, m = 1
8 Correct 1 ms 1880 KB n = 20, m = 5
9 Correct 1 ms 1880 KB n = 18, m = 3
10 Correct 1 ms 1884 KB n = 17, m = 2
11 Correct 1 ms 1884 KB n = 20, m = 2
12 Correct 1 ms 1884 KB n = 17, m = 4
13 Correct 1 ms 1884 KB n = 17, m = 6
14 Correct 1 ms 1880 KB n = 17, m = 1
15 Correct 1 ms 1884 KB n = 17, m = 4
16 Correct 1 ms 1884 KB n = 13, m = 3
17 Correct 1 ms 1884 KB n = 18, m = 4
18 Correct 1 ms 1884 KB n = 20, m = 10
19 Correct 1 ms 1884 KB n = 19, m = 10
20 Correct 1 ms 1884 KB n = 100, m = 5
21 Correct 1 ms 1880 KB n = 90, m = 3
22 Correct 1 ms 1884 KB n = 86, m = 2
23 Correct 1 ms 1884 KB n = 81, m = 4
24 Correct 1 ms 1880 KB n = 89, m = 10
25 Correct 1 ms 1884 KB n = 81, m = 23
26 Correct 1 ms 1884 KB n = 86, m = 8
27 Correct 1 ms 1884 KB n = 53, m = 22
28 Correct 1 ms 1884 KB n = 89, m = 35
29 Correct 1 ms 1884 KB n = 63, m = 25
30 Correct 1 ms 1884 KB n = 100, m = 50
31 Correct 1 ms 1880 KB n = 99, m = 50
32 Incorrect 1 ms 1884 KB char #0 differ - expected: '?', found: '_'
33 Halted 0 ms 0 KB -