QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#104945#6309. AqrejeffqiWA 112ms5768kbC++232.0kb2023-05-12 16:17:012023-05-12 16:17:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-12 16:17:02]
  • 评测
  • 测评结果:WA
  • 用时:112ms
  • 内存:5768kb
  • [2023-05-12 16:17:01]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for (int i = (a); i <= (b); ++i)
#define drep(i,a,b) for (int i = (a); i >= (b); --i)
#define LL long long
#define pii pair<int,int>
#define pll pair<LL,LL>
#define fi first
#define se second
#define mp make_pair
#define vi vector<int>
#define eb emplace_back
#define all(v) v.begin(),v.end()
#define sz(v) ((int)v.size())
using namespace std;
LL read() {
	LL x = 0,y = 1; char ch = getchar(); while (!isdigit(ch)) {if (ch == '-') y = -y; ch = getchar();}
	while (isdigit(ch)) {x = x*10+ch-'0'; ch = getchar();} return x*y;
}
const int tst = 0,rd = 1; int getflg = 0;
namespace qiqi {
	const int N = 1e3+5; int n,m,cnt,id[N][N],a[N][N];
	struct DSU {
		vi fa; void init(int n) {fa.assign(n+1,0); iota(all(fa),0);}
		int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
		void merge(int x,int y) {
			x = find(x); y = find(y);
			if (x == y) return;
			fa[y] = x;
		}
	} dsu;
	bool valid(int x,int y) {return x >= 1 && x <= n && y >= 1 && y <= m;}
	pair<int,vi> dfs(int x,vi p) {
		pair<int,vi> ans = mp(0,vi());
		if (x == 4) {
			int cnt = 0,flg = 1,fir = 0;
			rep(i,1,n) rep(j,1,m) {
				cnt += a[i][j] = p[i%4] != j%4;
			}
			dsu.init(n*m);
			rep(i,1,n) rep(j,1,m) if (a[i][j]) {
				if (valid(i+1,j) && a[i+1][j]) dsu.merge(id[i][j],id[i+1][j]);
				if (valid(i,j+1) && a[i][j+1]) dsu.merge(id[i][j],id[i][j+1]);
			}
			rep(i,1,n) rep(j,1,m) if (a[i][j]) {

			}
			rep(i,1,n) rep(j,1,m) if (a[i][j]) {
				if (!fir) fir = dsu.find(id[i][j]);
				else flg &= fir == dsu.find(id[i][j]);
			}
			if (flg) ans = mp(cnt,p);
		}
		else {
			rep(i,0,3) {
				p[x] = i;
				ans = max(ans,dfs(x+1,p));
			}
		}
		return ans;
	}
	void main() {
		n = read(); m = read(); cnt = 0;
		rep(i,1,n) rep(j,1,m) id[i][j] = ++cnt;
		pair<int,vi> ans = dfs(0,vi(4));
		printf("%d\n",ans.fi);
		rep(i,1,n) {
			rep(j,1,m) {
				printf("%d",ans.se[i%4] != j%4);
			}
			puts("");
		}
	}
}
int main() {
	int T = read(); while (T--) qiqi::main(); return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 5680kb

input:

3
2 2
3 4
3 8

output:

4
11
11
9
1101
1101
0111
18
11011101
11011101
01110111

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 112ms
memory: 5768kb

input:

361
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 20
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 16
3 17
3 18
3 19
3 20
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
4 14
4 15
4 16
4 17
4 18
4 19
4 20
5 2
5 3
5 4
5 5
5 6
5 7
5 8
5 9
5 1...

output:

4
11
11
6
111
111
6
1101
0111
8
10111
11101
9
110111
011101
11
1011101
1110111
12
11011101
01110111
14
101110111
111011101
15
1101110111
0111011101
17
10111011101
11101110111
18
110111011101
011101110111
20
1011101110111
1110111011101
21
11011101110111
01110111011101
23
101110111011101
1110111011101...

result:

wrong answer (0, 0) to (3, 0) are the same (test case 39)