#include <bits/stdc++.h>
#include "vision.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b){a = b; return true;}
return false;
}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b){a = b; return true;}
return false;
}
template <class T>
void printArr(T& a, string separator = " ", string finish = "\n"){
for(auto i: a) cout << i << separator;
cout << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
// namespace Interactor{
// vector<bool> a;
// int m_cnt = 0, o_cnt = 0;
// void add_not(int x){
// m_cnt++; o_cnt++;
// a.push_back(!a[x]);
// }
// void add_or(vector<int> x){
// m_cnt++; o_cnt += x.size();
// int ans = 0;
// for(int i: x) ans = ans || a[i];
// a.push_back(ans);
// }
// void add_and(vector<int> x){
// m_cnt++; o_cnt += x.size();
// int ans = 1;
// for(int i: x) ans = ans && a[i];
// a.push_back(ans);
// }
// void add_xor(vector<int> x){
// m_cnt++; o_cnt += x.size();
// printArr(x);
// int ans= 0;
// for(int i: x) ans = ans ^ a[i];
// a.push_back(ans);
// }
vector<int> get_pref(vector<int> a, int &memory){
int n = a.size();
vector<int> pref(n);
pref[0] = a[0];
for(int i= 1; i<n; ++i){
pref[i] = memory++;
vector<int> cu = {pref[i-1], a[i]};
add_or(cu);
}
return pref;
}
vector<int> get_suff(vector<int> a, int &memory){
int n = a.size();
vector<int> suff(n);
suff[n-1] = a[n-1];
for(int i= n-2; i>=0; --i){
suff[i] = memory++;
vector<int> cu = {suff[i+1], a[i]};
add_or(cu);
}
return suff;
}
int memory;
vector<int> dia1, dia2, pref_dia1, pref_dia2, suff_dia1, suff_dia2;
int check(int n, int m, int k){
vector<int> d_dia1, d_dia2;
for(int i = 0; i+k<n+m-1; ++i){
d_dia1.push_back(memory++);
d_dia1.push_back(memory++);
vector<int> cu1 = {dia1[i], suff_dia1[i + k]};
add_and(cu1);
vector<int> cu2 = {pref_dia1[i], dia1[i + k]};
add_and(cu2);
}
for(int i = 0; i+k<n+m-1; ++i){
d_dia2.push_back(memory++);
d_dia2.push_back(memory++);
vector<int> cu1 = {dia2[i], suff_dia2[i + k]};
add_and(cu1);
vector<int> cu2 = {pref_dia2[i], dia2[i + k]};
add_and(cu2);
}
vector<int> cu = d_dia1;
for(int i: d_dia2) cu.push_back(i);
add_or(cu);
return memory++;
}
void construct_network(int n, int m, int k){
memory = n * m;
#define toIdx(i, j) ((i) * m + (j))
// vector<vector<int>> row_cell(n), col_cell(m);
// for(int i= 0; i<n; ++i) for(int j =0; j<m; ++j){
// row_cell[i].push_back(toIdx(i, j));
// col_cell[j].push_back(toIdx(i, j));
// }
vector<vector<int>> dia1_cell(n + m - 1), dia2_cell(n+m-1);
for(int i= 0; i<n; ++i) for(int j= 0; j<m; ++j){
dia1_cell[i+j].push_back(toIdx(i, j));
dia2_cell[n-i-1+j].push_back(toIdx(i, j));
}
// vector<int> row(n), col(m);
dia1.resize(n+m-1), dia2.resize(n+m-1);
// for(int i = 0; i<n; ++i) {
// add_or(row_cell[i]);
// row[i] = memory++;
// }
// for(int i = 0; i<m; ++i) {
// add_or(col_cell[i]);
// col[i] = memory++;
// }
for(int i = 0; i<n+m-1; ++i) {
add_or(dia1_cell[i]);
dia1[i] = memory++;
}
for(int i = 0; i<n+m-1; ++i) {
add_or(dia2_cell[i]);
dia2[i] = memory++;
}
pref_dia1 = get_pref(dia1, memory), suff_dia1 = get_suff(dia1, memory);
pref_dia2 = get_pref(dia2, memory), suff_dia2 = get_suff(dia2, memory);
int x = check(n, m, k);
int y = check(n, m, k+1);
add_not(y);
y = memory++;
vector<int> cu = {x, y};
add_and(cu);
}
// bool solve(int n, int m){
// m_cnt = o_cnt = 0;
// a.clear();
// a.resize(n * m);
// vector<pair<int, int>> black;
// for(int i = 0; i<2; ++i){
// while(true){
// int x = rngesus(0, n*m-1);
// if (a[x]) continue;
// a[x] = true;
// black.push_back({x / m, x % m});
// break;
// }
// }
// int k = rngesus(1, n + m - 2);
// construct_network(n, m, k);
// return a.back() == (k == abs(black[0].first - black[1].first) + abs(black[0].second - black[1].second));
// }
// }
// int main(void){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// int n, m; cin >> n >> m;
// int t= 100;
// int rate = 0;
// for(int iteration = 1; iteration <= t; ++iteration){
// cout << "Iteration #" << iteration << "\n";
// bool verdict = Interactor::solve(n, m);
// if (verdict) cout << "AC" << endl;
// else cout << "WA" << endl;
// rate += verdict;
// cout << Interactor::m_cnt << " " << Interactor::o_cnt << "\n";
// }
// cout << rate << "\n";
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
WA in grader: Instruction with no inputs |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
WA in grader: Instruction with no inputs |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
WA in grader: Instruction with no inputs |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
WA in grader: Instruction with no inputs |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Output is correct |
| 2 |
Correct |
2 ms |
440 KB |
Output is correct |
| 3 |
Correct |
2 ms |
600 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
440 KB |
WA in grader: Instruction with no inputs |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
WA in grader: Instruction with no inputs |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
2076 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
604 KB |
Output is correct |
| 4 |
Correct |
3 ms |
692 KB |
Output is correct |
| 5 |
Correct |
2 ms |
600 KB |
Output is correct |
| 6 |
Correct |
2 ms |
688 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1240 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1240 KB |
Output is correct |
| 9 |
Correct |
13 ms |
2100 KB |
Output is correct |
| 10 |
Incorrect |
0 ms |
348 KB |
WA in grader: Instruction with no inputs |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
WA in grader: Instruction with no inputs |
| 3 |
Halted |
0 ms |
0 KB |
- |
