이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "vision.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i,a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 410;
const int LG = 9;
int get_xor(int *x, int l, int r) {
if(l == 0) return x[r];
return add_xor({x[r], x[l - 1]});
}
int get_or(int x[MAXN][LG], int l, int r) {
int k = __lg(r - l + 1);
return add_or({x[l][k], x[r - (1 << k) + 1][k]});
// vector<int> v;
// For(i, l, r) v.eb(x[i]);
// return add_or(v);
}
vector<vector<int>> dia1; // x + y, [0, H + W - 2]
vector<vector<int>> dia2; // x - y + W - 1, [0, H + W - 2]
int xor1[MAXN], xor2[MAXN];
int or1[MAXN][LG], or2[MAXN][LG];
int check(int k) {
int n = sz(dia1);
vector<int> v;
For(i, 0, n - k - 1) {
// or = 1, xor = 0 => 2 black cells
v.eb(add_xor({
get_or(or1, i, i + k),
get_xor(xor1, i, i + k)
}));
}
int a = add_or(v);
v.clear();
For(i, 0, n - k - 1) {
// or = 1, xor = 0 => 2 black cells
v.eb(add_xor({
get_or(or2, i, i + k),
get_xor(xor2, i, i + k)
}));
}
int b = add_or(v);
return add_and({a, b});
}
void construct_network(int H, int W, int K) {
// std::vector<int> Ns;
// Ns = {0, 1};
// int a = add_and(Ns);
// Ns = {0, a};
// int b = add_or(Ns);
// Ns = {0, 1, b};
// int c = add_xor(Ns);
// add_not(c);
int n = H + W - 1;
dia1.resize(n);
dia2.resize(n);
For(i, 0, H - 1) For(j, 0, W - 1) {
int id = i * W + j;
dia1[i + j].eb(id);
dia2[i - j + W - 1].eb(id);
}
xor1[0] = add_xor(dia1[0]);
xor2[0] = add_xor(dia2[0]);
For(i, 1, n - 1) {
dia1[i].eb(xor1[i - 1]);
xor1[i] = add_xor(dia1[i]);
dia1[i].pop_back();
dia2[i].eb(xor2[i - 1]);
xor2[i] = add_xor(dia2[i]);
dia2[i].pop_back();
}
For(i, 0, n - 1) {
or1[i][0] = add_or(dia1[i]);
or2[i][0] = add_or(dia2[i]);
}
For(j, 0, LG - 2) For(i, 0, n - 1) {
or1[i][j + 1] = or1[i][j];
or2[i][j + 1] = or2[i][j];
if(i + (1 << j) < n) {
or1[i][j + 1] = add_or({or1[i][j], or1[i + (1 << j)][j]});
or2[i][j + 1] = add_or({or2[i][j], or2[i + (1 << j)][j]});
}
}
int a = check(K);
int b = check(K - 1);
b = add_not(b);
add_and({a, b});
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |