QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#104945 | #6309. Aqre | jeffqi | WA | 112ms | 5768kb | C++23 | 2.0kb | 2023-05-12 16:17:01 | 2023-05-12 16:17:02 |
Judging History
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)