QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#308351 | #8018. 染色 | Xiaohuba | 35 | 1ms | 3788kb | C++23 | 4.3kb | 2024-01-19 23:21:36 | 2024-01-19 23:21:36 |
Judging History
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]);
assert(b[cur]._Find_first() == i);
For(j, 1, N * N) if (j != cur && b[j][i]) b[j] ^= b[cur];
cur++, qwq.eb(i);
}
while (cur <= N * N)
if (b[cur++][N * N + 1])
return puts("-1"), void();
// cerr << cur << ' ' << N * N << '\n';
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 - 1 << ' ' << j - 1
<< '\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;
}
// For(k, 1, N * N) cerr << b[id(i, j)][k];
// cerr << " | " << b[id(i, j)][N * N + 1] << '\n';
}
solve();
// cerr << "> " << b[1][N * N + 1] << ' ' << b[1][1] << endl;
// For(i, 1, N * N) cerr << ans[i];
}
} // namespace
signed main() { return solver_main(), 0; }
詳細信息
Test #1:
score: 5
Accepted
time: 0ms
memory: 3584kb
input:
2 0 0 1 1 1 0 1 0 0 0 0 0 1 1 1 0
output:
7 0 0 1 0 1 3 2 1 3 1 3 2 3 3
result:
ok n=4
Test #2:
score: 5
Accepted
time: 0ms
memory: 3516kb
input:
2 0 0 0 1 1 0 0 0 1 1 0 1 1 0 1 1
output:
8 0 0 1 3 2 0 2 2 2 3 3 0 3 1 3 3
result:
ok n=4
Test #3:
score: 5
Accepted
time: 1ms
memory: 3572kb
input:
2 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1
output:
8 0 1 0 3 1 0 1 2 2 0 2 2 2 3 3 3
result:
ok n=4
Test #4:
score: 5
Accepted
time: 0ms
memory: 3568kb
input:
2 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1 0
output:
10 0 1 0 3 1 1 1 2 1 3 2 0 2 1 2 3 3 0 3 3
result:
ok n=4
Test #5:
score: 5
Accepted
time: 1ms
memory: 3512kb
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:
133 0 1 0 2 0 6 0 9 0 11 0 12 0 13 0 14 0 15 1 1 1 5 1 6 1 9 1 11 1 12 1 13 1 14 1 15 2 1 2 2 2 6 2 8 2 9 2 10 2 12 2 14 2 15 3 0 3 1 3 3 3 8 3 11 3 12 3 15 4 1 4 2 4 3 4 5 4 6 4 7 4 11 4 14 5 2 5 3 5 5 5 7 5 9 5 11 5 12 5 13 6 1 6 4 6 5 6 6 6 8 6 11 6 13 6 14 7 2 7 4 7 6 7 8 7 9 7 10 7 11 7 15 8 1 ...
result:
ok n=16
Test #6:
score: 5
Accepted
time: 1ms
memory: 3724kb
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:
120 0 5 0 7 0 8 0 9 0 12 1 0 1 3 1 10 1 12 1 13 2 1 2 2 2 6 2 11 3 0 3 1 3 2 3 4 3 5 3 7 3 10 3 12 4 0 4 5 4 7 4 13 4 14 5 0 5 1 5 3 5 4 5 5 5 6 5 7 5 14 6 4 6 5 6 8 6 12 6 13 6 14 7 0 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 9 7 10 7 11 7 13 7 15 8 1 8 5 8 8 8 10 8 11 8 14 8 15 9 1 9 2 9 4 9 8 9 10 9 12 9 14 ...
result:
ok n=16
Test #7:
score: 5
Accepted
time: 1ms
memory: 3780kb
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:
123 0 0 0 1 0 3 0 7 0 14 1 2 1 3 1 8 1 9 1 12 2 2 2 3 2 5 2 6 2 8 2 11 2 14 3 0 3 1 3 2 3 3 3 5 3 7 3 9 3 10 3 12 3 14 4 0 4 1 4 3 4 6 4 7 4 8 4 14 4 15 5 7 5 9 5 14 5 15 6 1 6 5 6 6 6 8 6 9 6 12 7 0 7 2 7 7 7 8 7 10 7 11 8 2 8 4 8 7 8 9 8 10 8 13 8 15 9 0 9 2 9 5 9 6 9 7 9 9 9 12 9 15 10 0 10 1 10 ...
result:
ok n=16
Test #8:
score: 0
Wrong Answer
time: 0ms
memory: 3576kb
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: 3568kb
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:
1 0 0
result:
wrong answer wa
Test #10:
score: 0
Wrong Answer
time: 1ms
memory: 3580kb
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: 3596kb
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:
1 0 0
result:
wrong answer wa
Test #12:
score: 0
Wrong Answer
time: 1ms
memory: 3784kb
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: 3592kb
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:
1 0 0
result:
wrong answer wa
Test #14:
score: 0
Wrong Answer
time: 0ms
memory: 3712kb
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:
1 0 0
result:
wrong answer wa
Test #15:
score: 0
Wrong Answer
time: 0ms
memory: 3572kb
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: 1ms
memory: 3504kb
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:
1 0 0
result:
wrong answer wa
Test #17:
score: 0
Wrong Answer
time: 1ms
memory: 3772kb
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: 3536kb
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:
0
result:
wrong answer wa
Test #19:
score: 0
Wrong Answer
time: 1ms
memory: 3464kb
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: 0ms
memory: 3788kb
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