mayoko’s diary

プロコンとかいろいろ。

Looksery Cup 2015 B. Looksery Party

この解法本番考えたけど棄却してしまった…

解法

予想があたっている人がいたらその人を選ぶようにすると必ずうまく行く。

string board[105];
int a[105];
int cnt[105];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> board[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> select;
    while (1) {
        bool update = false;
        for (int i = 0; i < n; i++) {
            if (cnt[i] == a[i]) {
                update = true;
                select.push_back(i);
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == '1') {
                        cnt[j]++;
                    }
                }
            }
        }
        if (!update) break;
    }
    for (int i = 0; i < n; i++) {
        if (cnt[i] == a[i]) {
            cout << -1 << endl;
            return 0;
        }
    }
    sort(select.begin(), select.end());
    cout << select.size() << endl;
    for (int el : select) {
        cout << el+1 << " ";
    }
    cout << endl;
    return 0;
}