Codeforces#344 Div2 B問題

Created in: 2016-03-05 Author: iray_tno Category: Tags: Computer_a, 競プロ_a, やるだけ_a

はじめに

Codeforces Round #344 Div. 2 Prob. B. Print Check

問題:http://codeforces.com/contest/631/problem/B

行か列を一気に色(数字で表現)で塗る。最後の状態を出力する。

考え方

各行、各列で最後に塗られた色と、塗られた時間を記録する。各要素は属する行と列の遅く塗られたほうの色になる。計算量はO(n*m + k)。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>

using namespace std;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);

    int n,m,k;
    cin >> n >> m >> k;

    vector<int> row_color(n,0),row_last(n,0);
    vector<int> col_color(m,0),col_last(m,0);
    for(int i = 0; i < k; ++i){
        int task_id,rc,a;
        cin >> task_id >> rc >> a;
        rc--;
        bool is_row = false;
        if(task_id==1) is_row = true;

        if(is_row){
            row_color[rc] = a;
            row_last[rc] = i+1;
        }else{
            col_color[rc] = a;
            col_last[rc] = i+1;
        }
    }

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(j!=0) cout << " ";
            int num = 0;
            if(col_last[j]<row_last[i]){
                num = row_color[i];
            }else{
                num = col_color[j];
            }

            cout << num;
        }
        cout << endl;
    }

    return 0;
}
comments powered by Disqus