QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #150604 | #6380. LaLa and Divination Magic | LeticiaFCS | RE | 1ms | 3824kb | C++14 | 8.9kb | 2023-08-25 21:33:26 | 2023-08-25 21:33:27 |
Judging History
answer
#include"bits/stdc++.h"
using lint = int64_t;
constexpr int MOD = int(1e9) + 7;
constexpr int INF = 0x63636363;
constexpr int NINF = 0xcfcfcfcf;
constexpr lint LINF = 0x6363636363636363;
using namespace std;
struct scc_t {
int n, t, scc_num;
vector<vector<int>> adj;
vector<int> low, id, stk, in_stk, cc_id;
scc_t(const vector<vector<int>>& g) : n(int(g.size())), t(0), scc_num(0),
adj(g), low(n,-1), id(n,-1), in_stk(n, false), cc_id(n) {}
template<class F> void dfs(int cur, F f) {
id[cur] = low[cur] = t++;
stk.push_back(cur);
in_stk[cur] = true;
for (int nxt : adj[cur]) {
if (id[nxt] == -1) {
dfs(nxt, f);
low[cur] = min(low[cur], low[nxt]);
} else if (in_stk[nxt])
low[cur] = min(low[cur], id[nxt]);
}
if (low[cur] == id[cur]) {
vector<int> cc; cc.reserve(stk.size());
while (true) {
int v = stk.back(); stk.pop_back();
in_stk[v] = false;
cc.push_back(v);
cc_id[v] = scc_num;
if (v == cur) break;
} f(cc); scc_num ++;
}
}
template<class F> void solve(F f) {
stk.reserve(n);
for (int r = 0; r < n; ++r)
if (id[r] == -1) dfs(r, f);
}
};
const int M = 4002;
using B = bitset<M>;
B mat[M], matRev[M];
int always[M];
struct TwoSat {
int N;
vector<vector<int>> gr;
vector<int> values; // 0 = false, 1 = true
TwoSat(int n = 0) : N(n), gr(2*n) {}
int add_var() { // (optional)
gr.emplace_back();
gr.emplace_back();
return N++;
}
void either(int f, int j) {
f = max(2*f, -1-2*f);
j = max(2*j, -1-2*j);
gr[f].push_back(j^1);
gr[j].push_back(f^1);
}
void implies(int f, int j) { either(~f, j); }
void set_value(int x) { either(x, x); }
void at_most_one(const vector<int>& li) { // (optional)
if (int(li.size()) <= 1) return;
int cur = ~li[0];
for (int i = 2; i < int(li.size()); ++i) {
int next = add_var();
either(cur, ~li[i]);
either(cur, next);
either(~li[i], next);
cur = ~next;
}
either(cur, ~li[1]);
}
int solve() {
scc_t s(gr);
vector<int> ordem; ordem.reserve(2*N);
s.solve([&ordem](const vector<int> &v){
ordem.insert(ordem.end(), v.begin(), v.end());
} );
values.assign(N, -1);
for (int i = 0; i < N; ++i) if (s.cc_id[2*i] == s.cc_id[2*i+1]) return 0;
for (int i = 0; i < N; ++i){
if (s.cc_id[2*i] < s.cc_id[2*i+1]) values[i] = false;
else values[i] = true;
}
reverse(ordem.begin(), ordem.end());
vector<B> adj(2*N);
vector<B> alcanca(2*N);
for(int o =0; o<2*N; o++){
int u = ordem[o];
for(int v : gr[u]){
adj[u][v] = true;
alcanca[u][v] = true;
}
}
for(int o = 2*N-1; o >= 0; o--){
int u = ordem[o];
for(int v : gr[u])
alcanca[u] |= alcanca[v];
alcanca[u][u] = false;
}
vector<vector<int>> adjAlc(2*N);
for(int u = 0; u < 2*N; u++){
for(int v=0; v<2*N; v++){
if(alcanca[u][v])
adjAlc[u].push_back(v);
}
}
vector<bool> settado(2*N);
vector<bool> valor(2*N);
for(int u =0; u<2*N; u++){
int x = 2*u, notx = 2*u+1;
if(alcanca[x][notx]){
settado[x] = settado[notx] = true;
valor[x] = false;
valor[notx] = true;
for(int v = 0; v < 2*N; v++)
if(alcanca[notx][v]){
settado[v] = settado[v^1] = true;
valor[v] = true;
valor[v^1] = false;
}
} else if(alcanca[notx][x]){
settado[x] = settado[notx] = true;
valor[x] = true;
valor[notx] = false;
for(int v = 0; v < 2*N; v++)
if(alcanca[x][v]){
settado[v] = settado[v^1] = true;
valor[v] = true;
valor[v^1] = false;
}
}
}
int ans = 0;
auto count_sol = [&](int o, auto &&self) -> void {
if(o == 2*N){
ans++;
// cout<<"SOL \n";
// for(int u=0; u<N; u++){
// cout<<u<<" "<<valor[2*u]<<" "<<valor[2*u+1]<<"\n";
// }
return;
}
int u = ordem[o];
if(settado[u]){
self(o+1, self);
} else {
vector<int> alc;
bool ok = true;
if(ok)
for(int v : adjAlc[u]){
if(settado[v] && valor[v] == false){
ok = false;
break;
}
if(!settado[v]){
settado[v] = settado[v^1] = true;
valor[v] = true;
valor[v^1] = false;
alc.push_back(v);
}
}
settado[u] = settado[u^1] = true;
if(ok){
valor[u] = true;
valor[u^1] = false;
self(o+1, self);
}
for(int v : alc){
settado[v] = settado[v^1] = false;
}
valor[u] = false;
valor[u^1] = true;
self(o+1, self);
settado[u] = settado[u^1] = false;
}
};
count_sol(0, count_sol);
return ans;
}
};
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
cin>>n>>m;
for(int j=0; j<m; j++){
always[j] = -1;
}
for(int i =0; i<n; i++){
string s; cin>>s;
for(int j=0; j<m; j++){
mat[j][i] = int(s[j] - '0');
matRev[j][i] = !mat[j][i];
}
}
TwoSat sat(m);
vector<tuple<int, int, int>> op;
op.reserve(2*m);
for(int u =0; u<m; u++){
if(int c = mat[u].count(); c == n){
sat.either(u, u);
op.emplace_back(u, u, 4);
always[u] = 1;
} else if(c == 0){
sat.either(~u, ~u);
op.emplace_back(u, u, 1);
always[u] = 0;
}
}
for(int u =0; u<m; u++){
for(int v=u+1; v<m; v++){
if((~always[u]) && (~always[v])) continue;
vector<vector<int>> ok(2, vector<int>(2));
int cnt = 0;
if(( matRev[u] & matRev[v]).count() ){
ok[0][0] = true;
cnt++;
}
if(( matRev[u] & mat[v]).count() ){
ok[0][1] = true;
cnt++;
}
if(( mat[u] & matRev[v]).count() ){
ok[1][0] = true;
cnt++;
}
if(( mat[u] & mat[v]).count() ){
ok[1][1] = true;
cnt++;
}
if(cnt == 4) continue;
if(!ok[0][0]){
sat.implies(~u, v);
sat.implies(~v, u);
op.emplace_back(u, v, 4);
}
if(!ok[0][1]){
sat.implies(~u, ~v);
sat.implies(v, u);
op.emplace_back(u, v, 2);
}
if(!ok[1][0]){
sat.implies(u, v);
sat.implies(~v, ~u);
op.emplace_back(u, v, 3);
}
if(!ok[1][1]){
sat.implies(u, ~v);
sat.implies(v, ~u);
op.emplace_back(u, v, 1);
}
// cout<<"u "<<u<<" v "<<v<<"\n";
// for(int i=0;i<2; i++){
// for(int j=0;j<2; j++){
// if(ok[i][j])
// cout<<" "<<i<<" "<<j<<"\n";
// }
// }
}
}
if(int count_sol = sat.solve(); count_sol == n){
cout<<op.size()<<'\n';
for(const auto &[u,v,t] : op)
cout<<u<<' '<<v<<' '<<t<<'\n';
} else {
cout<<"-1\n";
}
return 0;
}
/*
1-either(~x, ~y): x -> ~y, y -> ~x
2-either(x, ~y): ~x -> ~y, y -> x
3-either(~x, y): x -> y, ~y -> ~x
4-either(x, y): ~x -> y, ~y -> x
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3596kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #2:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
3 3 101 011 111
output:
6 2 2 4 0 1 4 0 2 4 0 2 3 1 2 4 1 2 3
result:
ok Kout = 6, Kans = 6
Test #3:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #4:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #5:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #6:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #7:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #8:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #9:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
1 1 1
output:
1 0 0 4
result:
ok Kout = 1, Kans = 1
Test #10:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
1 1 0
output:
1 0 0 1
result:
ok Kout = 1, Kans = 1
Test #11:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #12:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #13:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
2 4 0111 0010
output:
12 0 0 1 2 2 4 0 1 3 0 1 1 0 3 3 0 3 1 1 2 4 1 2 3 1 3 2 1 3 3 2 3 4 2 3 2
result:
ok Kout = 12, Kans = 15
Test #14:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #15:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
4 2 10 11 01 00
output:
0
result:
ok Kout = 0, Kans = 0
Test #16:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
2 1 1 0
output:
0
result:
ok Kout = 0, Kans = 0
Test #17:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
2 4 0010 1000
output:
12 1 1 1 3 3 1 0 1 2 0 1 1 0 2 4 0 2 1 0 3 2 0 3 1 1 2 3 1 2 1 2 3 2 2 3 1
result:
ok Kout = 12, Kans = 15
Test #18:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
2 5 11101 00000
output:
21 3 3 1 0 1 2 0 1 3 0 2 2 0 2 3 0 3 2 0 3 1 0 4 2 0 4 3 1 2 2 1 2 3 1 3 2 1 3 1 1 4 2 1 4 3 2 3 2 2 3 1 2 4 2 2 4 3 3 4 3 3 4 1
result:
ok Kout = 21, Kans = 21
Test #19:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
5 4 0010 1001 0011 0101 1011
output:
-1
result:
ok Kout = -1, Kans = -1
Test #20:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
3 2 01 00 10
output:
1 0 1 1
result:
ok Kout = 1, Kans = 1
Test #21:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
3 2 10 11 00
output:
1 0 1 2
result:
ok Kout = 1, Kans = 1
Test #22:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
2 1 0 1
output:
0
result:
ok Kout = 0, Kans = 0
Test #23:
score: -100
Runtime Error
input:
3 27 111010110011101010011110110 010001110100000110100101101 000011111000000010011111001