【題解】Codeforces 1492E. Almost Fault-Tolerant Database

#include <iostream>
#include <vector>
using namespace std;
 
const int maxn = 250005;
int n, m, edit, arr[maxn];
vector <int> v[maxn];
 
bool f(int x){
    if (x == n) return true;
    int cnt = 0;
    vector <int> pos;
    for (int j = 0; j < m; j++){
        if (v[0][j] != v[x][j]){
            cnt++;
            pos.push_back(j);
        }
    }
    if (cnt <= 2) return f(x+1);
    if (edit + (cnt-2) > 2) return false;
    if (cnt == 3){
        edit += 1;
        for (auto j:pos){
            if (v[0][j] != arr[j]) continue;
            v[0][j] = v[x][j];
            if (f(1)) return true;
            v[0][j] = arr[j];
        }
        edit -= 1;
        return false;
    }
    if (cnt == 4){
        edit += 2;
        for (int i = 0; i < pos.size(); i++){
            if (v[0][pos[i]] != arr[pos[i]]) continue;
            v[0][pos[i]] = v[x][pos[i]];
            for (int j = i+1; j < pos.size(); j++){
                if (v[0][pos[j]] != arr[pos[j]]) continue;
                v[0][pos[j]] = v[x][pos[j]];
                if (f(1)) return true;
                v[0][pos[j]] = arr[pos[j]];
            }
            v[0][pos[i]] = arr[pos[i]];
        }
        edit -= 2;
        return false;
    }
    return false;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int j = 0; j < m; j++){
        cin >> arr[j];
        v[0].push_back(arr[j]);
    }
    for (int i = 1; i < n; i++){
        int cnt = 0;
        for (int j = 0, a; j < m; j++){
            cin >> a;
            v[i].push_back(a);
            if (v[i][j] != v[0][j]) cnt++;
        }
        if (cnt >= 5){
            cout << "No\n";
            return 0;
        }
    }
    if (!f(1)) cout << "No\n";
    else {
        cout << "Yes\n";
        for (int j = 0; j < m; j++){
            cout << v[0][j] << " ";
        }
        cout << "\n";
    }
}