| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 579489 | keta_tsimakuridze | Vision Program (IOI19_vision) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "vision.h"
using namespace std;
const int N = 2e5 + 5;
int id_or[N], id_xor[N], cur;
vector<int> X;
void add_and(vector<int> Ns) {
int x = 1;
for(int i = 0; i < Ns.size(); i++) {
x &= X[Ns[i]];
}
X.push_back(x);
}
void add_or(vector<int> Ns) {
int x = 0;
for(int i = 0; i < Ns.size(); i++) {
x |= X[Ns[i]];
}
X.push_back(x);
}
void add_xor(vector<int> Ns) {
int x = 0;
for(int i = 0; i < Ns.size(); i++) {
x ^= X[Ns[i]];
}
X.push_back(x);
}
void add_not(int N) {
X.push_back(1^X[N]);
}
vector<int> d[N];
int go(int n, int k) {
vector<int> V;
for(int i = 0; i < n; i++) {
id_or[i] = ++cur; add_or(d[i]);
id_xor[i] = ++cur; add_xor(d[i]);
add_not(cur); ++cur;
add_and({cur, id_or[i]});
V.push_back(++cur);
}
for(int i = k; i < n; i++) {
vector<int> v;
for(int j = i - k ; j <= i; j++) {
v.push_back(id_or[j]);
}
++cur;
add_or(v);
++cur;
add_xor(v);
add_not(cur); ++cur;
add_and({cur, cur - 2}); ++cur;
V.push_back(cur);
}
add_or(V); ++cur;
return cur;
}
void calc(int n, int m,int k) {
for(int i = 0; i < n + m; i++) d[i].clear();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
d[i - j + m - 1].push_back(i * m + j);
}
}
int id1 = go(n + m - 1, k);
for(int i = 0; i < n + m; i++) {
d[i].clear();
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
d[i + j].push_back(i * m + j);
}
}
int id2 = go(n + m - 1, k);
add_and({id1, id2}); ++cur;
}
void construct_network(int H, int W, int K) {
cur = H * W; --cur;
calc(H, W, K);
int pcur = cur;
calc(H, W, K - 1);
add_xor({pcur, cur});
}
/*
int main() {
int H, W, K;
assert(3 == scanf("%d%d%d", &H, &W, &K));
for(int i = 0; i < H; i++) {
for(int j = 0; j < W; j++) {
int a;
cin >> a;
X.push_back(a);
}
}
construct_network(H, W, K);
cout << X.back() << endl;
}*/