Submission #832688

#	Time	Username	Problem	Language	Result	Execution time	Memory
832688		GordonRemzi007	Game (eJOI20_game)	C++17	80 / 100	24 ms	7892 KiB

game

#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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 20