QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#308341 | #8018. 染色 | Xiaohuba | 0 | 1ms | 3812kb | C++23 | 3.9kb | 2024-01-19 23:03:25 | 2024-01-19 23:03:26 |
answer
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#if __cplusplus < 201400
#warning "Please use c++14 or higher."
#define INLINE_V
#define REGISTER_V register
#define CPP14CONSTEXPR
#define gcd __gcd
#define CPP14ENABLE_IF
#elif __cplusplus < 201700
#define INLINE_V
#define REGISTER_V
#define CPP14CONSTEXPR constexpr
#define gcd __gcd
#define CPP14ENABLE_IF ,enable_if_t<_is_integer<T>, int> = 0
#else
#define INLINE_V inline
#define REGISTER_V
#define CPP14CONSTEXPR constexpr
#define CPP14ENABLE_IF ,enable_if_t<_is_integer<T>, int> = 0
#endif
#if !defined(_WIN32) && !defined(LOCK_GETCHAR)
#define getchar getchar_unlocked
#endif
#define il inline
#define mkp make_pair
#define fi first
#define se second
#define For(i,j,k) for(REGISTER_V int i=(j);i<=(k);++i) // NOLINT
#define ForDown(i,j,k) for(REGISTER_V int i=(j);i>=(k);--i) // NOLINT
#define pb push_back
#define eb emplace_back
#ifndef ONLINE_JUDGE
#define FileIO(filename) freopen(filename".in","r",stdin);freopen(filename".out","w",stdout)
#else
#define FileIO(filename)
#endif
using ll = long long;
// using lll = __int128_t;
using uint = unsigned int;
using ull = unsigned long long;
// using ulll = __uint128_t;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#if __cplusplus >= 201400
template <class T> INLINE_V constexpr bool _is_integer = numeric_limits<T>::is_integer;
// template <> INLINE_V constexpr bool _is_integer<__int128> = true;
// template <> INLINE_V constexpr bool _is_integer<__uint128_t> = true;
template <> INLINE_V constexpr bool _is_integer<bool> = false;
template <> INLINE_V constexpr bool _is_integer<char> = false;
template <class T CPP14ENABLE_IF>
INLINE_V constexpr T INF = numeric_limits<T>::max() >> 1;
#endif
template<typename T> constexpr il T sq(const T & x){return x*x;}
template<typename T> CPP14CONSTEXPR il void cmin(T & x, const T &y){x=min(x,y);}
template<typename T> CPP14CONSTEXPR il void cmax(T & x, const T &y){x=max(x,y);}
template<typename T> CPP14CONSTEXPR il T qpow(T x, ull y, T mod){T ans=1;x%=mod;while(y){if(y&1)(ans*=x)%=mod;(x*=x)%=mod;y>>=1;}return ans;}
template<typename T> CPP14CONSTEXPR il T qpow(T x, ull y){T ans=1;while(y){if(y&1)ans*=x;x*=x;y>>=1;}return ans;}
template<typename T CPP14ENABLE_IF> il void read(T &x){ x=0;int f=1;int c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=f;}
template<typename T, typename ... Args> il void read(T &x, Args &... y){ read(x);read(y...); }
// File head end
// clang-format on
namespace {
constexpr ll MAXN = (1 << 4) + 5;
int n, N, a[MAXN][MAXN], dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
bitset<MAXN * MAXN> b[MAXN * MAXN];
bitset<MAXN * MAXN> ans;
#define id(x, y) (((x)-1) * N + y)
il void solve() {
int cur = 1;
vector<int> qwq;
For(i, 1, N * N) {
int row = cur;
while (row <= N * N && !b[row][i])
row++;
if (row == N * N + 1)
continue;
swap(b[row], b[cur]);
For(j, 1, N * N) if (j != cur) b[j] ^= b[cur];
cur++, qwq.eb(i);
}
while (cur <= N * N)
if (b[cur++][N * N + 1])
return puts("-1"), void();
int cnt = 0;
for (int x : qwq)
ans[x] = b[x][N * N + 1] ^ b[x][x], cnt += ans[x];
cout << cnt << '\n';
For(i, 1, N) For(j, 1, N) if (ans[id(i, j)]) cout << i << ' ' << j << '\n';
}
il void solver_main() {
read(n), N = 1 << n;
For(i, 1, N) For(j, 1, N) read(a[i][j]);
For(i, 1, N) For(j, 1, N) {
b[id(i, j)][N * N + 1] = a[i][j];
b[id(i, j)][id(i, j)] = 1;
For(_, 0, 3) {
int x = i + dx[_], y = j + dy[_];
if (!x)
x = N;
if (!y)
y = N;
if (x == N + 1)
x = 1;
if (y == N + 1)
y = 1;
b[id(i, j)][id(x, y)] = 1;
}
}
solve();
}
} // namespace
signed main() { return solver_main(), 0; }
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3572kb
input:
2 0 0 1 1 1 0 1 0 0 0 0 0 1 1 1 0
output:
5 1 1 2 4 3 3 4 1 4 3
result:
wrong answer Integer 4 violates the range [0, 3]
Test #2:
score: 0
Wrong Answer
time: 1ms
memory: 3528kb
input:
2 0 0 0 1 1 0 0 0 1 1 0 1 1 0 1 1
output:
8 1 1 2 1 2 4 3 1 3 2 4 1 4 2 4 4
result:
wrong answer Integer 4 violates the range [0, 3]
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 3596kb
input:
2 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1
output:
7 2 1 2 3 2 4 4 1 4 2 4 3 4 4
result:
wrong answer Integer 4 violates the range [0, 3]
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 3536kb
input:
2 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1 0
output:
6 1 1 1 2 2 4 3 3 4 3 4 4
result:
wrong answer Integer 4 violates the range [0, 3]
Test #5:
score: 0
Wrong Answer
time: 0ms
memory: 3612kb
input:
4 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 1 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 0 1 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 0 1 1 0 1 1 0 0 1 0 0 1 0 1 ...
output:
122 1 2 1 4 1 7 1 9 1 10 1 12 1 14 1 15 2 1 2 5 2 6 2 9 2 10 2 13 2 14 2 15 3 3 3 4 3 5 3 7 3 9 3 10 3 11 3 12 3 16 4 2 4 3 4 4 4 6 4 8 4 9 4 10 5 1 5 2 5 4 5 14 5 15 6 3 6 6 6 7 6 8 6 9 6 11 6 13 7 5 7 6 7 10 7 14 7 16 8 7 8 10 8 11 8 12 8 13 8 14 8 15 9 1 9 2 9 3 9 9 9 10 9 12 9 14 9 15 10 1 10 2 ...
result:
wrong answer Integer 16 violates the range [0, 15]
Test #6:
score: 0
Wrong Answer
time: 0ms
memory: 3572kb
input:
4 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 ...
output:
127 1 3 1 6 1 10 1 12 1 15 1 16 2 1 2 2 2 3 2 4 2 7 2 9 2 14 2 15 3 2 3 5 3 6 3 9 3 16 4 2 4 8 4 13 4 14 4 15 5 2 5 6 5 8 5 11 5 12 5 13 5 15 5 16 6 2 6 3 6 4 6 10 6 11 7 1 7 3 7 4 7 5 7 6 7 8 7 11 7 12 7 13 7 15 7 16 8 2 8 3 8 7 8 8 8 10 8 14 8 16 9 2 9 5 9 6 9 7 9 8 9 9 9 10 9 13 9 14 9 15 9 16 10...
result:
wrong answer Integer 16 violates the range [0, 15]
Test #7:
score: 0
Wrong Answer
time: 0ms
memory: 3608kb
input:
4 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 1 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 ...
output:
135 1 1 1 2 1 3 1 5 1 6 1 10 1 11 1 12 2 1 2 4 2 5 2 6 2 7 2 10 2 12 2 13 2 14 3 1 3 2 3 5 3 6 3 8 3 9 3 11 3 12 3 13 3 15 4 3 4 7 4 9 4 11 4 12 4 13 4 15 4 16 5 3 5 4 5 8 5 9 5 10 5 12 5 13 5 15 5 16 6 1 6 3 6 5 6 6 6 9 6 12 6 13 6 14 6 16 7 3 7 4 7 6 7 8 7 13 7 15 8 2 8 5 8 8 8 10 8 13 8 14 9 1 9 ...
result:
wrong answer Integer 16 violates the range [0, 15]
Test #8:
score: 0
Wrong Answer
time: 0ms
memory: 3580kb
input:
7 1 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 0 1 0 0 1 ...
output:
0
result:
wrong answer wa
Test #9:
score: 0
Wrong Answer
time: 0ms
memory: 3584kb
input:
7 1 1 0 1 0 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1 0 1 0 1 1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 ...
output:
0
result:
wrong answer wa
Test #10:
score: 0
Wrong Answer
time: 0ms
memory: 3468kb
input:
7 1 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 ...
output:
0
result:
wrong answer wa
Test #11:
score: 0
Wrong Answer
time: 0ms
memory: 3588kb
input:
11 1 1 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 0 1...
output:
0
result:
wrong answer wa
Test #12:
score: 0
Wrong Answer
time: 0ms
memory: 3540kb
input:
11 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1...
output:
0
result:
wrong answer wa
Test #13:
score: 0
Wrong Answer
time: 1ms
memory: 3540kb
input:
11 1 0 1 0 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0...
output:
0
result:
wrong answer wa
Test #14:
score: 0
Wrong Answer
time: 0ms
memory: 3544kb
input:
11 1 1 0 1 1 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 0 0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 0 0 0 1...
output:
0
result:
wrong answer wa
Test #15:
score: 0
Wrong Answer
time: 0ms
memory: 3796kb
input:
11 1 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 0...
output:
0
result:
wrong answer wa
Test #16:
score: 0
Wrong Answer
time: 0ms
memory: 3740kb
input:
11 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1...
output:
0
result:
wrong answer wa
Test #17:
score: 0
Wrong Answer
time: 0ms
memory: 3540kb
input:
11 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0...
output:
0
result:
wrong answer wa
Test #18:
score: 0
Wrong Answer
time: 0ms
memory: 3812kb
input:
11 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1...
output:
1 1 1
result:
wrong answer wa
Test #19:
score: 0
Wrong Answer
time: 0ms
memory: 3536kb
input:
11 1 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 1 0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 1 0...
output:
0
result:
wrong answer wa
Test #20:
score: 0
Wrong Answer
time: 1ms
memory: 3812kb
input:
11 0 0 0 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 0 1 1 0 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 0 1 1 0...
output:
0
result:
wrong answer wa