oj.uz

Submission #578181

# Submission time Handle Problem Language Result Execution time Memory
578181 2022-06-16T07:20:16 Z johnf Mars (APIO22_mars) C++17
14 / 100
 17 ms 2312 KB 
#include "mars.h"
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

using ll = long long;
using ld = long double;
using vi = vector<int>;

template <class T>
bool uin(T &a, T b) {
    return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
    return a < b ? (a = b, true) : false;
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

namespace subn4 {
std::string process(std::vector<std::vector<std::string>> &a, int &row, int &col, int &phase, int &n) {
    int N = n * 2 + 1;
    string ans(100, '0');
    if (phase == 0) {
        // first phase
        fore(i, row, row + 2) {
            fore(j, col, col + 2) {
                if (a[i - row][j - col][0] == '1') {
                    ans[i * N + j] = '1';
                }
            }
        }
    } else {
        fore(i, row, row + 2) {
            fore(j, col, col + 2) {
                for0(k, 100) {
                    if (a[i - row][j - col][k] == '1') {
                        ans[k] = '1';
                    }
                }
            }
        }
    }
    debug(row, col, phase, ans);
    if (phase == n - 1) {
        // then lol
        const pair<int, int> d[] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
        vector<vector<int>> flag(N, vector<int>(N));
        int cnt = 0;
        for0(i, N) {
            for0(j, N) {
                if (!flag[i][j] && ans[i * N + j] == '1') {
                    cnt++;
                    queue<pair<int, int>> q;
                    q.emplace(i, j);
                    flag[i][j] = 1;
                    while (!q.empty()) {
                        int x, y;
                        tie(x, y) = q.front();
                        q.pop();
                        for (auto [dx, dy] : d) {
                            int nx = x + dx, ny = y + dy;
                            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                                if (!flag[nx][ny] && ans[nx * N + ny] == '1') {
                                    flag[nx][ny] = 1;
                                    q.emplace(nx, ny);
                                }
                            }
                        }
                    }
                }
            }
        }
        ans = string(100, '0');
        for0(i, 31) { ans[i] = '0' + (cnt >> i & 1); }
    }
    return ans;
}
}

std::string process(std::vector<std::vector<std::string>> a, int i, int j, int k, int n) {
    if (n <= 4) {
        return subn4::process(a, i, j, k, n);
    }
}

Compilation message

mars.cpp: In function 'std::string subn4::process(std::vector<std::vector<std::__cxx11::basic_string<char> > >&, int&, int&, int&, int&)':
mars.cpp:20:20: warning: statement has no effect [-Wunused-value]
   20 | #define debug(...) 42
      |                    ^~
mars.cpp:62:5: note: in expansion of macro 'debug'
   62 |     debug(row, col, phase, ans);
      |     ^~~~~
mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:103:1: warning: control reaches end of non-void function [-Wreturn-type]
  103 | }
      | ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2076 KB Output is correct
2 Correct 8 ms 2128 KB Output is correct
3 Correct 8 ms 2100 KB Output is correct
4 Correct 8 ms 2088 KB Output is correct
5 Correct 8 ms 2108 KB Output is correct
6 Correct 8 ms 2120 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2076 KB Output is correct
2 Correct 8 ms 2128 KB Output is correct
3 Correct 8 ms 2100 KB Output is correct
4 Correct 8 ms 2088 KB Output is correct
5 Correct 8 ms 2108 KB Output is correct
6 Correct 8 ms 2120 KB Output is correct
7 Correct 13 ms 1984 KB Output is correct
8 Correct 16 ms 2012 KB Output is correct
9 Correct 16 ms 2312 KB Output is correct
10 Correct 16 ms 2212 KB Output is correct
11 Correct 16 ms 1980 KB Output is correct
12 Correct 16 ms 2204 KB Output is correct
13 Correct 17 ms 2044 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2076 KB Output is correct
2 Correct 8 ms 2128 KB Output is correct
3 Correct 8 ms 2100 KB Output is correct
4 Correct 8 ms 2088 KB Output is correct
5 Correct 8 ms 2108 KB Output is correct
6 Correct 8 ms 2120 KB Output is correct
7 Correct 13 ms 1984 KB Output is correct
8 Correct 16 ms 2012 KB Output is correct
9 Correct 16 ms 2312 KB Output is correct
10 Correct 16 ms 2212 KB Output is correct
11 Correct 16 ms 1980 KB Output is correct
12 Correct 16 ms 2204 KB Output is correct
13 Correct 17 ms 2044 KB Output is correct
14 Runtime error 1 ms 456 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2076 KB Output is correct
2 Correct 8 ms 2128 KB Output is correct
3 Correct 8 ms 2100 KB Output is correct
4 Correct 8 ms 2088 KB Output is correct
5 Correct 8 ms 2108 KB Output is correct
6 Correct 8 ms 2120 KB Output is correct
7 Correct 13 ms 1984 KB Output is correct
8 Correct 16 ms 2012 KB Output is correct
9 Correct 16 ms 2312 KB Output is correct
10 Correct 16 ms 2212 KB Output is correct
11 Correct 16 ms 1980 KB Output is correct
12 Correct 16 ms 2204 KB Output is correct
13 Correct 17 ms 2044 KB Output is correct
14 Runtime error 1 ms 456 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2076 KB Output is correct
2 Correct 8 ms 2128 KB Output is correct
3 Correct 8 ms 2100 KB Output is correct
4 Correct 8 ms 2088 KB Output is correct
5 Correct 8 ms 2108 KB Output is correct
6 Correct 8 ms 2120 KB Output is correct
7 Correct 13 ms 1984 KB Output is correct
8 Correct 16 ms 2012 KB Output is correct
9 Correct 16 ms 2312 KB Output is correct
10 Correct 16 ms 2212 KB Output is correct
11 Correct 16 ms 1980 KB Output is correct
12 Correct 16 ms 2204 KB Output is correct
13 Correct 17 ms 2044 KB Output is correct
14 Runtime error 1 ms 456 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2076 KB Output is correct
2 Correct 8 ms 2128 KB Output is correct
3 Correct 8 ms 2100 KB Output is correct
4 Correct 8 ms 2088 KB Output is correct
5 Correct 8 ms 2108 KB Output is correct
6 Correct 8 ms 2120 KB Output is correct
7 Correct 13 ms 1984 KB Output is correct
8 Correct 16 ms 2012 KB Output is correct
9 Correct 16 ms 2312 KB Output is correct
10 Correct 16 ms 2212 KB Output is correct
11 Correct 16 ms 1980 KB Output is correct
12 Correct 16 ms 2204 KB Output is correct
13 Correct 17 ms 2044 KB Output is correct
14 Runtime error 1 ms 456 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2076 KB Output is correct
2 Correct 8 ms 2128 KB Output is correct
3 Correct 8 ms 2100 KB Output is correct
4 Correct 8 ms 2088 KB Output is correct
5 Correct 8 ms 2108 KB Output is correct
6 Correct 8 ms 2120 KB Output is correct
7 Correct 13 ms 1984 KB Output is correct
8 Correct 16 ms 2012 KB Output is correct
9 Correct 16 ms 2312 KB Output is correct
10 Correct 16 ms 2212 KB Output is correct
11 Correct 16 ms 1980 KB Output is correct
12 Correct 16 ms 2204 KB Output is correct
13 Correct 17 ms 2044 KB Output is correct
14 Runtime error 1 ms 456 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2076 KB Output is correct
2 Correct 8 ms 2128 KB Output is correct
3 Correct 8 ms 2100 KB Output is correct
4 Correct 8 ms 2088 KB Output is correct
5 Correct 8 ms 2108 KB Output is correct
6 Correct 8 ms 2120 KB Output is correct
7 Correct 13 ms 1984 KB Output is correct
8 Correct 16 ms 2012 KB Output is correct
9 Correct 16 ms 2312 KB Output is correct
10 Correct 16 ms 2212 KB Output is correct
11 Correct 16 ms 1980 KB Output is correct
12 Correct 16 ms 2204 KB Output is correct
13 Correct 17 ms 2044 KB Output is correct
14 Runtime error 1 ms 456 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2076 KB Output is correct
2 Correct 8 ms 2128 KB Output is correct
3 Correct 8 ms 2100 KB Output is correct
4 Correct 8 ms 2088 KB Output is correct
5 Correct 8 ms 2108 KB Output is correct
6 Correct 8 ms 2120 KB Output is correct
7 Correct 13 ms 1984 KB Output is correct
8 Correct 16 ms 2012 KB Output is correct
9 Correct 16 ms 2312 KB Output is correct
10 Correct 16 ms 2212 KB Output is correct
11 Correct 16 ms 1980 KB Output is correct
12 Correct 16 ms 2204 KB Output is correct
13 Correct 17 ms 2044 KB Output is correct
14 Runtime error 1 ms 456 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2076 KB Output is correct
2 Correct 8 ms 2128 KB Output is correct
3 Correct 8 ms 2100 KB Output is correct
4 Correct 8 ms 2088 KB Output is correct
5 Correct 8 ms 2108 KB Output is correct
6 Correct 8 ms 2120 KB Output is correct
7 Correct 13 ms 1984 KB Output is correct
8 Correct 16 ms 2012 KB Output is correct
9 Correct 16 ms 2312 KB Output is correct
10 Correct 16 ms 2212 KB Output is correct
11 Correct 16 ms 1980 KB Output is correct
12 Correct 16 ms 2204 KB Output is correct
13 Correct 17 ms 2044 KB Output is correct
14 Runtime error 1 ms 456 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -