QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#308342#8018. 染色Xiaohuba0 1ms3800kbC++234.0kb2024-01-19 23:03:592024-01-19 23:04:00

Judging History

This is the latest submission verdict.

  • [2024-01-19 23:04:00]
  • Judged
  • Verdict: 0
  • Time: 1ms
  • Memory: 3800kb
  • [2024-01-19 23:03:59]
  • Submitted

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 - 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;
    }
  }
  solve();
}
} // namespace

signed main() { return solver_main(), 0; }

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3596kb

input:

2
0 0 1 1
1 0 1 0
0 0 0 0
1 1 1 0

output:

5
0 0
1 3
2 2
3 0
3 2

result:

wrong answer wa

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 3592kb

input:

2
0 0 0 1
1 0 0 0
1 1 0 1
1 0 1 1

output:

8
0 0
1 0
1 3
2 0
2 1
3 0
3 1
3 3

result:

wrong answer wa

Test #3:

score: 0
Wrong Answer
time: 1ms
memory: 3604kb

input:

2
1 1 1 0
0 1 0 0
1 0 1 0
0 1 0 1

output:

7
1 0
1 2
1 3
3 0
3 1
3 2
3 3

result:

wrong answer wa

Test #4:

score: 0
Wrong Answer
time: 0ms
memory: 3604kb

input:

2
1 0 1 1
1 0 1 0
0 1 1 0
1 1 1 0

output:

6
0 0
0 1
1 3
2 2
3 2
3 3

result:

wrong answer wa

Test #5:

score: 0
Wrong Answer
time: 0ms
memory: 3608kb

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
0 1
0 3
0 6
0 8
0 9
0 11
0 13
0 14
1 0
1 4
1 5
1 8
1 9
1 12
1 13
1 14
2 2
2 3
2 4
2 6
2 8
2 9
2 10
2 11
2 15
3 1
3 2
3 3
3 5
3 7
3 8
3 9
4 0
4 1
4 3
4 13
4 14
5 2
5 5
5 6
5 7
5 8
5 10
5 12
6 4
6 5
6 9
6 13
6 15
7 6
7 9
7 10
7 11
7 12
7 13
7 14
8 0
8 1
8 2
8 8
8 9
8 11
8 13
8 14
9 0
9 1
9 8
9 12
...

result:

wrong answer wa

Test #6:

score: 0
Wrong Answer
time: 1ms
memory: 3592kb

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
0 2
0 5
0 9
0 11
0 14
0 15
1 0
1 1
1 2
1 3
1 6
1 8
1 13
1 14
2 1
2 4
2 5
2 8
2 15
3 1
3 7
3 12
3 13
3 14
4 1
4 5
4 7
4 10
4 11
4 12
4 14
4 15
5 1
5 2
5 3
5 9
5 10
6 0
6 2
6 3
6 4
6 5
6 7
6 10
6 11
6 12
6 14
6 15
7 1
7 2
7 6
7 7
7 9
7 13
7 15
8 1
8 4
8 5
8 6
8 7
8 8
8 9
8 12
8 13
8 14
8 15
9 1
9 ...

result:

wrong answer wa

Test #7:

score: 0
Wrong Answer
time: 1ms
memory: 3592kb

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
0 0
0 1
0 2
0 4
0 5
0 9
0 10
0 11
1 0
1 3
1 4
1 5
1 6
1 9
1 11
1 12
1 13
2 0
2 1
2 4
2 5
2 7
2 8
2 10
2 11
2 12
2 14
3 2
3 6
3 8
3 10
3 11
3 12
3 14
3 15
4 2
4 3
4 7
4 8
4 9
4 11
4 12
4 14
4 15
5 0
5 2
5 4
5 5
5 8
5 11
5 12
5 13
5 15
6 2
6 3
6 5
6 7
6 12
6 14
7 1
7 4
7 7
7 9
7 12
7 13
8 0
8 1
8 ...

result:

wrong answer wa

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: 3512kb

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: 3592kb

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: 3580kb

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: 3516kb

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: 0ms
memory: 3536kb

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: 3540kb

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: 3800kb

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: 3736kb

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: 3512kb

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: 3800kb

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
0 0

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: 0ms
memory: 3592kb

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