#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
int solveDiv(int N, int start, int K){
vector<int> v;
for(int i = 0; i < min(K, N-K); i++){
vector<int> w;
for(int j = i; j < N; j += K) w.push_back(start+j);
v.push_back(add_xor(w));
}
return add_not(add_or(v));
}
bool isPrimePower(int i){
int div = -1;
for(int j = 2; j < i; j++){
if(i % j == 0){
if(div == -1) div = j;
else if(j % div != 0) return false;
}
}
return true;
}
int solve1D(int N, vector<int> mult, int K){
vector<int> mu, div;
for(int i = 2*K; i < N; i += K){
if(isPrimePower(i)) mu.push_back(mult[i]);
}
for(int i = 1; i <= K; i++){
if(K % i == 0 && isPrimePower(i)) div.push_back(mult[i]);
}
int a = -1, b = -1;
if(!mu.empty()) a = add_not(add_or(mu));
if(!div.empty()) b = add_and(div);
if(a == -1) return b;
else return a;
return add_and({a, b});
}
void construct_network(int H, int W, int K) {
int row_start = -1, col_start = -1;
for(int i = 0; i < H; i++){
vector<int> v;
for(int j = 0; j < W; j++) v.push_back(i*W+j);
int x = add_or(v);
if(i == 0) row_start = x;
}
for(int j = 0; j < W; j++){
vector<int> v;
for(int i = 0; i < H; i++) v.emplace_back(i*W+j);
int x = add_or(v);
if(j == 0) col_start = x;
}
vector<int> row(H), col(W);
{ // k = 0
vector<int> v;
for(int i = 0; i < H; i++) v.push_back(row_start+i);
row[0] = add_xor(v);
v.clear();
for(int i = 0; i < W; i++) v.push_back(col_start+i);
col[0] = add_xor(v);
}
vector<int> multR(H), multC(W);
for(int k = 1; k < H; k++){
if(!isPrimePower(k)) continue;
multR[k] = solveDiv(H, row_start, k);
}
for(int k = 1; k < W; k++){
if(!isPrimePower(k)) continue;
multC[k] = solveDiv(W, col_start, k);
}
for(int k = 1; k < H; k++){
row[k] = solve1D(H, multR, k);
}
for(int k = 1; k < W; k++){
col[k] = solve1D(W, multC, k);
}
vector<int> todo;
for(int kr = 0; kr < H; kr++){
int kc = K-kr;
if(kc >= 0 && kc < W){
todo.push_back(add_and({row[kr], col[kc]}));
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
300 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
212 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
300 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
212 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
300 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
212 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
300 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
212 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
596 KB |
on inputs (0, 2), (0, 3), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
1628 KB |
on inputs (80, 199), (81, 199), expected 1, but computed 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
300 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
212 KB |
on inputs (0, 0), (0, 1), expected 1, but computed 0 |
| 6 |
Halted |
0 ms |
0 KB |
- |
