QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#308366#8018. 染色Xiaohuba35 1ms3720kbC++233.6kb2024-01-20 00:30:442024-01-20 00:30:44

Judging History

你现在查看的是最新测评结果

  • [2024-01-20 00:30:44]
  • 评测
  • 测评结果:35
  • 用时:1ms
  • 内存:3720kb
  • [2024-01-20 00:30:44]
  • 提交

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;
bitset<MAXN> a[MAXN], b[MAXN];
#define id(x, y) (((x)-1) * N + y)

il void solve() {
  while (n--) {
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        if (a[i][j]) {
          b[i].flip(j);
          b[i].flip((j + (1 << n)) & (N - 1));
          b[i].flip((N + j - (1 << n)) & (N - 1));
          b[(i + (1 << n)) & (N - 1)].flip(j);
          b[(N + i - (1 << n)) & (N - 1)].flip(j);
        }
    copy(b, b + N, a);
    for_each(b, b + N, [&](auto &src) { src.reset(); });
  }
}

il void solver_main() {
  read(n), N = 1 << n;
  int tmp = 0;
  For(i, 0, N - 1) For(j, 0, N - 1) read(tmp), a[i][j] = tmp;
  solve();
  int ans = 0;
  for_each(a, a + N, [&](const auto &src) { ans += src.count(); });
  cout << ans << '\n';
  For(i, 0, N - 1) For(j, 0, N - 1) if (a[i][j]) cout << i << ' ' << j << '\n';
}
} // namespace

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

详细

Test #1:

score: 5
Accepted
time: 1ms
memory: 3688kb

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

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

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

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

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

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

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
Runtime Error

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:


result:


Test #9:

score: 0
Runtime Error

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:


result:


Test #10:

score: 0
Runtime Error

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:


result:


Test #11:

score: 0
Runtime Error

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:


result:


Test #12:

score: 0
Runtime Error

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:


result:


Test #13:

score: 0
Runtime Error

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:


result:


Test #14:

score: 0
Runtime Error

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:


result:


Test #15:

score: 0
Runtime Error

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:


result:


Test #16:

score: 0
Runtime Error

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:


result:


Test #17:

score: 0
Runtime Error

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:


result:


Test #18:

score: 0
Runtime Error

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:


result:


Test #19:

score: 0
Runtime Error

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:


result:


Test #20:

score: 0
Runtime Error

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:


result: