oj.uz

Submission #832688

# Submission time Handle Problem Language Result Execution time Memory
832688 2023-08-21T13:53:06 Z GordonRemzi007 Game (eJOI20_game) C++17
80 / 100
 24 ms 7892 KB 
#include <bits/stdc++.h>
#define NULL INT_MIN
using namespace std;

const int MAX = 20*20;
int n, m, cnt, loop, rl, rr;
vector<string> h, v;
vector<vector<bool>> visited;
struct Pos {
    Pos(int xi, int yi):x(xi),y(yi){}
    int x, y;
};
Pos temp(0, 0);
queue<Pos> q;
vector<Pos> c;
bool srt(Pos a, Pos b) {
    return a.x < b.x;
}
int pow(int a, int b){
    int ans = 1;
    while(b){
        if (b&1) ans = ans*a;
        b /= 2;
        a = a*a;
    }
    return ans;
}

vector<string> bits;
vector<vector<int>> memo;
int recurs(int i, int j) {
    //cout << i << " " << j << "\n";
    int cnt, temp;
    if(j) {
        memo[i][1] = INT_MAX;
        for(int k = 0; k < c.size(); k++) {
            if(bits[i][k] == '0') {
                cnt = i|(1<<k);
                //cout << memo[cnt][0] << " " << memo[cnt][1] << "\n";
                temp = (memo[cnt][0] == NULL ? recurs(cnt, 0) : memo[cnt][0])+c[k].x;
                if(c[k].y || c[k].x >= 3) temp = max(temp, (memo[cnt][1] == NULL ? recurs(cnt, 1): memo[cnt][1])-(c[k].y ? 8 : 4)+c[k].x );
                memo[i][j] = min(memo[i][j], temp);
            }
        }
    } else {
        memo[i][0] = INT_MIN;
        for(int k = 0; k < c.size(); k++) {
            if(bits[i][k] == '0') {
                cnt = i|(1<<k);
                //cout << cnt << " " << k << "e\n";
                //cout << memo[cnt][0] << " " << memo[cnt][1] << "\n";
                temp = (memo[cnt][1] == NULL ? recurs(cnt, 1) : memo[cnt][1])-c[k].x;
                if(c[k].y || c[k].x >= 3) temp = min(temp, (memo[cnt][0] == NULL ? recurs(cnt, 0) : memo[cnt][0])+(c[k].y ? 8 : 4)-c[k].x);
                memo[i][j] = max(memo[i][j], temp);
            }
        }
    }
    return memo[i][j];
}

int main() {
    cin >> n >> m;
    h = vector<string>(n+1), v = vector<string>(n), visited = vector<vector<bool>>(n, vector<bool>(m, false));
    for(int i = 0; i <= n; i++) cin >> h[i];
    for(int i = 0; i < n; i++) cin >> v[i];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(!visited[i][j] && (h[i][j] == '0' || h[i+1][j] == '0' || v[i][j] == '0' || v[i][j+1] == '0')) {
                cnt = 0, loop = 1;
                q.push({i, j});
                while(q.size()) {
                    temp = q.front();
                    q.pop();
                    if(visited[temp.x][temp.y]) continue;
                    cnt++;
                    visited[temp.x][temp.y] = true;
                    if((temp.x == 0 && h[temp.x][temp.y] == '0') || (temp.x == n-1 && h[temp.x+1][temp.y] == '0') || (temp.y == 0 && v[temp.x][temp.y] == '0') || (temp.y == m-1 && v[temp.x][temp.y+1] == '0')) loop = 0;
                    if(temp.x > 0 && h[temp.x][temp.y] == '0' && !visited[temp.x-1][temp.y]) q.push(Pos(temp.x-1, temp.y));
                    if(temp.x < n-1 && h[temp.x+1][temp.y] == '0' && !visited[temp.x+1][temp.y]) q.push(Pos(temp.x+1, temp.y));
                    if(temp.y > 0 && v[temp.x][temp.y] == '0' && !visited[temp.x][temp.y-1]) q.push(Pos(temp.x, temp.y-1));
                    if(temp.y < m-1 && v[temp.x][temp.y+1] == '0' && !visited[temp.x][temp.y+1]) q.push(Pos(temp.x, temp.y+1));
                }
                c.push_back(Pos(cnt, loop));
            }
        }
    }
    sort(c.begin(), c.end(), srt);
    //dp
    memo = vector<vector<int>>(pow(2, c.size()), vector<int>(2, NULL));
    bits = vector<string>(memo.size(), string(c.size(), '0'));
    for(int i = 1; i < memo.size(); i++) {
        loop = true;
        for(int j = 0; j < c.size(); j++) {
            if(loop) {
                if(bits[i-1][j] == '0') {
                    loop = false;
                    bits[i][j] = '1';
                } else bits[i][j] = '0';
            } else bits[i][j] = bits[i-1][j];
        }
    }
    memo[memo.size()-1] = {0, 0};
    cout << recurs(0,0) << "\n";

    //for(auto i : c) cout << i.x << " " << i.y << "\n";
    //for(auto i : memo) cout << i[0] << " " << i[1] << "\n";

}

Compilation message

game.cpp:2: warning: "NULL" redefined
    2 | #define NULL INT_MIN
      | 
In file included from /usr/include/uchar.h:29,
                 from /usr/include/c++/10/cuchar:53,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:61,
                 from game.cpp:1:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:392: note: this is the location of the previous definition
  392 | #define NULL __null
      | 
game.cpp: In function 'int recurs(int, int)':
game.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Pos>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int k = 0; k < c.size(); k++) {
      |                        ~~^~~~~~~~~~
game.cpp:47:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Pos>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for(int k = 0; k < c.size(); k++) {
      |                        ~~^~~~~~~~~~
game.cpp: In function 'int main()':
game.cpp:91:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i = 1; i < memo.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
game.cpp:93:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Pos>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for(int j = 0; j < c.size(); j++) {
      |                        ~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 296 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 304 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 300 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 280 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 10 ms 3112 KB Output is correct
10 Correct 24 ms 7892 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 596 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 296 KB Output is correct
5 Correct 0 ms 296 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 300 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 304 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 0 ms 300 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 0 ms 300 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 280 KB Output is correct
36 Correct 1 ms 296 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 0 ms 212 KB Output is correct
44 Correct 1 ms 212 KB Output is correct
45 Correct 0 ms 212 KB Output is correct
46 Correct 0 ms 212 KB Output is correct
47 Correct 0 ms 212 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 1 ms 212 KB Output is correct
52 Correct 1 ms 340 KB Output is correct
53 Correct 1 ms 468 KB Output is correct
54 Correct 1 ms 340 KB Output is correct
55 Correct 1 ms 468 KB Output is correct
56 Correct 1 ms 340 KB Output is correct
57 Correct 1 ms 596 KB Output is correct
58 Correct 1 ms 340 KB Output is correct
59 Correct 10 ms 3112 KB Output is correct
60 Correct 24 ms 7892 KB Output is correct
61 Correct 1 ms 340 KB Output is correct
62 Correct 1 ms 340 KB Output is correct
63 Correct 1 ms 340 KB Output is correct
64 Correct 1 ms 468 KB Output is correct
65 Correct 1 ms 596 KB Output is correct
66 Runtime error 2 ms 468 KB Execution killed with signal 6
67 Halted 0 ms 0 KB -