QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #101654 | #6380. LaLa and Divination Magic | willow# | WA | 3ms | 7836kb | C++14 | 2.2kb | 2023-04-30 17:06:49 | 2023-04-30 17:06:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2005;
char s[maxn][maxn];
int n, m, cnt;
bitset<maxn>w[maxn][2], f[2][2][maxn];
vector<pair<pair<int, int>, int> > ans;
bitset<4000>to[maxn], h, pre;
void Solve(int now, bitset<4000> cur) {
bitset<4000> w = cur & h, x = cur & (h << 1);
// for(int i = 0; i < 2 * m; ++ i)
// cerr << w[i];
// cerr << endl;
// for(int i = 0; i < 2 * m; ++ i)
// cerr << x[i];
// cerr << endl;
x |= (w << 1);
// for(int i = 0; i < 2 * m; ++ i)
// cerr << x[i];
// cerr << endl;
if(x.count() != m)
return;
// cerr << "S" << now << endl;
// for(int i = 0; i < 2 * m; ++ i)
// cerr << cur[i];
// cerr << endl;
if(now >= m) {
++ cnt;
if(cnt > n)
exit(0 * puts("-1"));
return;
}
// cerr << cur[now * 2] << " " << cur[now * 2 + 1] << endl;
// for(int i = 0; i < 2 * m; ++ i)
// cerr << to[now * 2][i];
// cerr << endl;
// for(int i = 0; i < 2 * m; ++ i)
// cerr << to[now * 2 + 1][i];
// cerr << endl;
if(cur[now * 2])
Solve(now + 1, cur & to[now * 2]);
if(cur[now * 2 + 1])
Solve(now + 1, cur & to[now * 2 + 1]);
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++ i) {
scanf("%s", s[i]);
for(int j = 0; j < m; ++ j) {
w[i][s[i][j] - '0'][j] = 1;
}
for(int j = 0; j < m; ++ j) {
if(s[i][j] - '0') {
f[1][0][j] |= w[i][0];
f[1][1][j] |= w[i][1];
}
else {
f[0][0][j] |= w[i][0];
f[0][1][j] |= w[i][1];
}
}
}
for(int i = 0; i < 2 * m; ++ i)
to[i].set();
for(int a = 0; a < 2; ++ a)
for(int b = 0; b < 2; ++ b)
for(int i = 0; i < m; ++ i)
for(int j = i; j < m; ++ j) {
if(i == j && a != b)
continue;
if(f[a ^ 1][b ^ 1][i][j])
continue;
// i canbe a or j canbe b
to[i * 2 + (a ^ 1)][j * 2 + (b ^ 1)] = 0;
to[j * 2 + (b ^ 1)][i * 2 + (a ^ 1)] = 0;
ans.push_back({{i, j}, a + b * 2 + 1});
}
for(int i = 0; i < m; ++ i)
to[m * 2][m * 2 + 1] = to[m * 2 + 1][m * 2] = 0, h[i * 2] = 1;
for(int i = 0; i < 2 * m; ++ i)
pre[i] = 1;
Solve(0, pre);
printf("%d\n", (int)ans.size());
for(auto w : ans)
printf("%d %d %d\n", w.first.first, w.first.second, w.second);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7736kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #2:
score: 0
Accepted
time: 3ms
memory: 7836kb
input:
3 3 101 011 111
output:
6 0 2 3 1 2 3 0 1 4 0 2 4 1 2 4 2 2 4
result:
ok Kout = 6, Kans = 6
Test #3:
score: 0
Accepted
time: 2ms
memory: 7688kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #4:
score: 0
Accepted
time: 0ms
memory: 7724kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #5:
score: 0
Accepted
time: 2ms
memory: 7768kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #6:
score: 0
Accepted
time: 3ms
memory: 7712kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #7:
score: 0
Accepted
time: 2ms
memory: 7684kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #8:
score: 0
Accepted
time: 2ms
memory: 7712kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #9:
score: -100
Wrong Answer
time: 1ms
memory: 7520kb
input:
1 1 1
output:
-1
result:
wrong answer Jury has a solution while the participant doesn't, Kans = 1