#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(v) ((int)v.size())
#define forn(i,n) for(int i = 0; i < n; ++i)
#define forbe(i,b,e) for(int i = b; i < e; ++i)
#define pb push_back
#define pry puts("YES")
#define prn puts("NO")
#define endl '\n'
#define fst first
#define scn second
const int K = 10;
int add_not(int N);
int add_and(vector<int> s);
int add_or(vector<int> s);
int add_xor(vector<int> s);
#ifdef ONPC
int cnt1, cnt2;
vector<int> table;
int
add_not(int N)
{
++cnt1;
++cnt2;
assert(N<sz(table));
if (table[N])
table.pb(0);
else
table.pb(1);
return sz(table)-1;
}
int
add_and(vector<int> s)
{
int ans = 0;
++cnt1;
cnt2 += sz(s);
for (int i = 0; i < sz(s); ++i)
assert(s[i] < sz(table));
for (int i = 0; i < sz(s); ++i)
ans += table[s[i]];
if (ans==sz(s))
table.pb(1);
else
table.pb(0);
return sz(table)-1;
}
int
add_or(vector<int> s)
{
int ans = 0;
++cnt1;
cnt2 += sz(s);
for (int i = 0; i < sz(s); ++i)
assert(s[i] < sz(table));
for (int i = 0; i < sz(s); ++i)
ans += table[s[i]];
if (ans>0)
table.pb(1);
else
table.pb(0);
return sz(table)-1;
}
int
add_xor(vector<int> s)
{
int ans = 0;
++cnt1;
cnt2 += sz(s);
for (int i = 0; i < sz(s); ++i)
assert(s[i] < sz(table));
for (int i = 0; i < sz(s); ++i)
ans += table[s[i]];
if (ans&1)
table.pb(1);
else
table.pb(0);
return sz(table)-1;
}
#endif
void
construct_network(int h, int w, int k)
{
vector<int> rowOR(h);
vector<int> colOR(w);
vector<int> bitx(K);
vector<int> bity(K);
vector<int> bitans(K);
int zero;
int z = 0;
int u1,u2,u3,u4;
vector<int> q;
vector<int> lastq;
vector<int> bigq;
q.resize(w);
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
q[j] = i * w + j;
}
rowOR[i] = add_or(q);
}
q.resize(h);
for (int i = 0; i < w; ++i) {
for (int j = 0; j < h; ++j) {
q[j] = j * w + i;
}
colOR[i] = add_or(q);
}
if (w * h > 2)
zero = add_and({0,1,2});
else
zero = add_not(0);
for (int i = 0; i < K; ++i) {
bitx[i] = zero;
bity[i] = zero;
}
/* Get y height */
q.clear();
for (int i = 0; i < h; ++i) {
q.pb(rowOR[i]);
bigq.pb(add_xor(q));
}
z = 0;
while (1) {
assert(z<10);
q = bigq;
bity[z] = add_xor(q);
if (q.size() == 1)
break;
bigq.clear();
for (int i = 0; i < sz(q)-1; i+=2) {
u1 = add_and({q[i],q[i+1]});
u2 = add_xor({q[i],q[i+1],bity[z]});
u3 = add_and({u2,q[i+1]});
bigq.pb(add_or({u1,u3}));
}
++z;
}
/* Get x height */
q.clear();
for (int i = 0; i < w; ++i) {
q.pb(colOR[i]);
bigq.pb(add_xor(q));
}
z = 0;
while (1) {
assert(z<10);
q = bigq;
bitx[z] = add_xor(q);
if (q.size() == 1)
break;
bigq.clear();
for (int i = 0; i < sz(q)-1; i+=2) {
u1 = add_and({q[i],q[i+1]});
u2 = add_xor({q[i],q[i+1],bitx[z]});
u3 = add_and({u2,q[i+1]});
bigq.pb(add_or({u1,u3}));
}
++z;
}
/* Do sum */
int lbit = zero;
for (int i = 0; i < K; ++i) {
bitans[i] = add_xor({lbit,bitx[i],bity[i]});
u1 = add_and({bitx[i],bity[i]});
u2 = add_and({bitx[i],lbit});
u3 = add_and({bity[i],lbit});
lbit = add_or({u1,u2,u3});
if ((k&(1<<i))==0) {
bitans[i] = add_not(bitans[i]);
}
}
add_and(bitans);
return;
}
#ifdef ONPC
void
generate()
{
int h = 200;
int w = 200;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
table.pb(0);
}
}
table[0] = 1;
table[600] = 1;
return;
}
void
solve()
{
generate();
construct_network(200,200,3);
cout << table[sz(table)-1] << endl;
cout << cnt1 << ' ' << cnt2 << endl;
}
int32_t
main()
{
int t = 1;
/* cin >> t; */
while(t--)
solve();
}
#endif
Compilation message
vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:114:18: warning: unused variable 'u4' [-Wunused-variable]
114 | int u1,u2,u3,u4;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
596 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
1700 KB |
on inputs (80, 199), (81, 199), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
