QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#147460#6380. LaLa and Divination MagicLeticiaFCSWA 1ms3592kbC++204.8kb2023-08-23 10:07:462023-08-25 01:32:00

Judging History

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

  • [2023-08-25 01:32:00]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3592kb
  • [2023-08-23 10:07:46]
  • 提交

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);
    }
};
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]);
    }
    bool solve() {
        scc_t s(gr);
        s.solve([](const vector<int> &v){ return; } );
        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;
        }
        return 1;
    }
};

const int M = 2002;
using B = bitset<M>;
B mat[M];
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin>>n>>m;
    for(int i =0; i<n; i++){
        string s; cin>>s;
        for(int j=0; j<m; j++){
            mat[i][j] = int(s[j] - '0');
        }
    }
    TwoSat sat(m);
    vector<tuple<int, int, int>> op;
    for(int u =0; u<m; u++){
        for(int v=u+1; v<m; v++){
            int mask = 0;
            for(int i =0; i<n; i++){
                if(~mat[i][u] & ~mat[i][v])
                    mask |= (1<<0);
                if(~mat[i][u] & mat[i][v])
                    mask |= (1<<1);
                if(mat[i][u] & ~mat[i][v])
                    mask |= (1<<2);
                if(mat[i][u] & mat[i][v])
                    mask |= (1<<3);
            }
            bool ok = false;
            if(mask == 15)
                continue;
            
            if( ~mask & (1<<3) ){
                int t = 1;
                sat.either(~u, ~v);
                op.emplace_back(u, v, t);
                ok = true;
            }if( ~mask & (1<<1) ){
                int t = 2;
                sat.either(u, ~v);
                op.emplace_back(u, v, t);
                ok = true;
            }if( ~mask & (1<<2) ){
                int t = 3;
                sat.either(~u, v);
                op.emplace_back(u, v, t);
                ok = true;
            }if( ~mask & (1<<0) ){
                int t = 4;
                sat.either(u, v);
                op.emplace_back(u, v, t);
                ok = true;
            }
            if(ok) continue;
            cout<<"NO\n";
            exit(0);            
        }
    }
    if(sat.solve()){
        cout<<op.size()<<'\n';
        for(const auto &[u,v,t] : op)
            cout<<u<<' '<<v<<' '<<t<<'\n';
    } else {
        cout<<"NO\n";
    }
    return 0;
}



/*


0 - 0 0
1 - 0 1
2 - 1 0
3 - 1 1


X or Y - 4 - (1,2,3)
0   1
1   0
1   1


X or ~Y - 2 - (0,2,3)
0   0
1   1
1   0

~X or Y - 3 - (0,1,3)
1   1
0   0
0   1

~X or ~Y - 1 - (0,1,2)
1   0
0   1
0   0
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3532kb

input:

2 1
1
0

output:

0

result:

ok Kout = 0, Kans = 0

Test #2:

score: 0
Accepted
time: 1ms
memory: 3460kb

input:

3 3
101
011
111

output:

5
0 1 4
0 2 3
0 2 4
1 2 3
1 2 4

result:

ok Kout = 5, Kans = 6

Test #3:

score: 0
Accepted
time: 1ms
memory: 3472kb

input:

2 1
0
1

output:

0

result:

ok Kout = 0, Kans = 0

Test #4:

score: 0
Accepted
time: 1ms
memory: 3532kb

input:

2 1
0
1

output:

0

result:

ok Kout = 0, Kans = 0

Test #5:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

2 1
1
0

output:

0

result:

ok Kout = 0, Kans = 0

Test #6:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

2 1
0
1

output:

0

result:

ok Kout = 0, Kans = 0

Test #7:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

2 1
0
1

output:

0

result:

ok Kout = 0, Kans = 0

Test #8:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

2 1
1
0

output:

0

result:

ok Kout = 0, Kans = 0

Test #9:

score: -100
Wrong Answer
time: 1ms
memory: 3580kb

input:

1 1
1

output:

0

result:

wrong answer The output contains more solutions than intended.