CSES - Datatähti 2026 alku

Submission details
Task:	Maalaus
Sender:	wolruso
Submission time:	2025-11-06 21:52:44 +0200
Language:	Rust (2021)
Status:	READY
Result:	58

Feedback
group	verdict	score
#1	ACCEPTED	10
#2	ACCEPTED	16
#3	ACCEPTED	32
#4	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.00 s	1, 3, 4	details
#2	ACCEPTED	0.00 s	3, 4	details
#3	ACCEPTED	0.00 s	1, 3, 4	details
#4	ACCEPTED	0.05 s	2, 4	details
#5	ACCEPTED	0.05 s	2, 4	details
#6	ACCEPTED	0.01 s	3, 4	details
#7	ACCEPTED	0.01 s	3, 4	details
#8	WRONG ANSWER	0.11 s	4	details
#9	WRONG ANSWER	0.14 s	4	details
#10	ACCEPTED	0.00 s	1, 3, 4	details
#11	ACCEPTED	0.00 s	1, 3, 4	details
#12	ACCEPTED	0.04 s	2, 4	details
#13	ACCEPTED	0.04 s	2, 4	details
#14	WRONG ANSWER	0.08 s	4	details
#15	WRONG ANSWER	0.11 s	4	details
#16	WRONG ANSWER	0.08 s	4	details
#17	WRONG ANSWER	0.11 s	4	details

Code

use std::{
    cmp::{Ordering, Reverse},
    collections::HashMap,
    io::stdin,
};

#[derive(Eq, PartialEq)]
enum PaintOrderType {
    Row,
    Column,
}
struct PaintOrder {
    typ: PaintOrderType,
    pos: usize,
    clr: usize,
}

fn o_iter(q: usize) -> impl Iterator<Item = PaintOrder> {
    (0..q).map(|_| {
        let mut l = String::new();
        stdin().read_line(&mut l).unwrap();
        let mut oitr = l.split(' ');
        let otyp = match oitr.next().unwrap() {
            "R" => PaintOrderType::Row,
            _ => PaintOrderType::Column,
        };
        let p = oitr.next().unwrap().parse::<usize>().unwrap() - 1;
        let c = oitr.next().unwrap().trim_end().parse::<usize>().unwrap() - 1;
        PaintOrder {
            typ: otyp,
            pos: p,
            clr: c,
        }
    })
}

fn tg_1(n: usize, m: usize, k: usize, q: usize) {
    let mut grid = Vec::with_capacity(n);
    for _ in 0..n {
        let mut v = Vec::with_capacity(m);
        for _ in 0..m {
            v.push(k);
        }
        grid.push(v);
    }
    for PaintOrder {
        typ: otyp,
        pos: p,
        clr: c,
    } in o_iter(q)
    {
        match otyp {
            PaintOrderType::Row => {
                for i in 0..m {
                    grid[p][i] = c;
                }
            }
            PaintOrderType::Column => {
                for i in 0..n {
                    grid[i][p] = c;
                }
            }
        }
    }
    let mut colors = Vec::with_capacity(k);
    for _ in 0..k {
        colors.push(0);
    }
    for i in 0..n {
        for j in 0..m {
            let c = grid[i][j];
            if c < k {
                colors[c] += 1;
            }
        }
    }
    println!(
        "{}",
        colors
            .into_iter()
            .map(|c| c.to_string())
            .collect::<Vec<String>>()
            .join(" ")
    );
}

fn tg_2(n: usize, m: usize, q: usize) {
    let mut orders: Vec<PaintOrder> = o_iter(q).collect();
    orders.sort_unstable_by(|o1, o2| match o1.typ {
        PaintOrderType::Row => match o2.typ {
            PaintOrderType::Row => o1.pos.cmp(&o2.pos),
            PaintOrderType::Column => Ordering::Less,
        },
        PaintOrderType::Column => match o2.typ {
            PaintOrderType::Row => Ordering::Greater,
            PaintOrderType::Column => o1.pos.cmp(&o2.pos),
        },
    });
    let mut row_count = 0;
    let mut column_count = 0;
    for (i, o) in orders.iter().enumerate() {
        if i == 0 || orders[i - 1].typ != o.typ || orders[i - 1].pos != o.pos {
            match o.typ {
                PaintOrderType::Row => row_count += 1,
                PaintOrderType::Column => column_count += 1,
            }
        }
    }
    let total = row_count * m + column_count * (n - row_count);
    println!("{}", total);
}

fn tg_3(n: usize, m: usize, k: usize, q: usize) {
    let mut clrs = Vec::with_capacity(k);
    for _ in 0..k {
        clrs.push(0);
    }

    let mut cm: HashMap<usize, (usize, usize)> = HashMap::with_capacity(q);
    let mut rm: HashMap<usize, (usize, usize)> = HashMap::with_capacity(q);
    let mut cs: Vec<isize> = Vec::with_capacity(q);
    let mut rs: Vec<isize> = Vec::with_capacity(q);
    let mut ic: Vec<isize> = Vec::with_capacity(q);
    let mut ir: Vec<isize> = Vec::with_capacity(q);

    for (i, o) in o_iter(q).enumerate() {
        match o.typ {
            PaintOrderType::Row => {
                if let Some(&(c, t)) = rm.get(&o.pos) {
                    let mut smod = m;
                    let s = (ic[t] + 1) as usize;
                    for j in s..cs.len() {
                        if cs[j] != -1 {
                            let cc = cm[&(cs[j] as usize)].0;
                            clrs[cc] -= 1;
                            smod -= 1;
                        }
                    }
                    clrs[c] -= smod;
                    rm.remove(&o.pos);
                    let oi = ir[t] as usize;
                    rs[oi] = -1;
                } else {
                    for (_, &(cc, _)) in &cm {
                        clrs[cc] -= 1;
                    }
                }
                clrs[o.clr] += m;
                rm.insert(o.pos, (o.clr, i));
                rs.push(o.pos as isize);
            }
            PaintOrderType::Column => {
                if let Some(&(c, t)) = cm.get(&o.pos) {
                    let mut smod = m;
                    let s = (ir[t] + 1) as usize;
                    for j in s..rs.len() {
                        if rs[j] != -1 {
                            let cc = rm[&(rs[j] as usize)].0;
                            clrs[cc] -= 1;
                            smod -= 1;
                        }
                    }
                    clrs[c] -= smod;
                    cm.remove(&o.pos);
                    let oi = ic[t] as usize;
                    cs[oi] = -1;
                } else {
                    for (_, &(cc, _p)) in &rm {
                        clrs[cc] -= 1;
                    }
                }
                clrs[o.clr] += n;
                cm.insert(o.pos, (o.clr, i));
                cs.push(o.pos as isize);
            }
        }
        ir.push(rs.len() as isize - 1);
        ic.push(cs.len() as isize - 1);
    }

    println!(
        "{}",
        clrs.into_iter()
            .map(|c| c.to_string())
            .collect::<Vec<String>>()
            .join(" ")
    );
}

fn tg_4(n: usize, m: usize, k: usize, q: usize) {
    let mut clrs = Vec::with_capacity(k);
    for _ in 0..k {
        clrs.push(0);
    }

    let mut cm: HashMap<usize, (usize, usize)> = HashMap::with_capacity(q);
    let mut rm: HashMap<usize, (usize, usize)> = HashMap::with_capacity(q);
    let mut c_counts: Vec<usize> = Vec::with_capacity(q);
    let mut r_counts: Vec<usize> = Vec::with_capacity(q);
    let mut sc_counts: Vec<usize> = Vec::with_capacity(q);
    let mut sr_counts: Vec<usize> = Vec::with_capacity(q);

    let mut cc = 0;
    let mut rc = 0;
    for (i, o) in o_iter(q).enumerate() {
        match o.typ {
            PaintOrderType::Row => {
                if let Some(&(_, t)) = rm.get(&o.pos) {
                    sr_counts.push(t);
                    rm.remove(&o.pos);
                }
                rc += 1; // must happen even if the row already existed before
                rm.insert(o.pos, (o.clr, i));
            }
            PaintOrderType::Column => {
                if let Some(&(_, t)) = cm.get(&o.pos) {
                    sc_counts.push(t);
                    cm.remove(&o.pos);
                }
                cc += 1;
                cm.insert(o.pos, (o.clr, i));
            }
        }
        r_counts.push(rc);
        c_counts.push(cc);
    }

    sr_counts.sort_unstable_by_key(|k| Reverse(*k));
    let mut r_dups = HashMap::with_capacity(sr_counts.len());
    for (i, t) in sr_counts.iter().enumerate() {
        *r_dups.entry(t).or_insert(0) = i;
    }
    sc_counts.sort_unstable_by_key(|k| Reverse(*k));
    let mut c_dups = HashMap::with_capacity(sc_counts.len());
    for (i, t) in sc_counts.iter().enumerate() {
        *c_dups.entry(t).or_insert(0) = i;
    }

    for (_, &(c, t)) in &cm {
        let mut smod = rc - r_counts[t];
        if sr_counts.len() > 0 && t + 1 <= sr_counts[0] {
            let dc = match r_dups.get(&(t + 1)) {
                Some(dt) => *dt,
                None => match sr_counts.binary_search_by(|v| v.cmp(&(t + 1)).reverse()) {
                    Ok(dt) => r_dups[&sr_counts[dt - 1]],
                    Err(dt) => r_dups[&sr_counts[dt - 1]],
                },
            };
            smod -= dc;
        }
        clrs[c] += n - smod;
    }

    for (_, &(c, t)) in &rm {
        let mut smod = cc - c_counts[t];
        if sc_counts.len() > 0 && t + 1 <= sc_counts[0] {
            let dc = match c_dups.get(&(t + 1)) {
                Some(dt) => *dt,
                None => match sc_counts.binary_search_by(|v| v.cmp(&(t + 1)).reverse()) {
                    Ok(dt) => c_dups[&sc_counts[dt - 1]],
                    Err(dt) => c_dups[&sc_counts[dt - 1]],
                },
            };
            smod -= dc;
        }
        clrs[c] += m - smod;
    }

    println!(
        "{}",
        clrs.into_iter()
            .map(|c| c.to_string())
            .collect::<Vec<String>>()
            .join(" ")
    );
}

fn main() {
    let mut l = String::new();
    stdin().read_line(&mut l).unwrap();
    let mut itr = l.split(' ');
    let n: usize = itr.next().unwrap().parse().unwrap();
    let m: usize = itr.next().unwrap().parse().unwrap();
    let k: usize = itr.next().unwrap().parse().unwrap();
    let q: usize = itr.next().unwrap().trim_end().parse().unwrap();
    if k > 1 {
        if n <= 10 && m <= 10 {
            tg_1(n, m, k, q);
        } else if k <= 2000 && q <= 2000 {
            tg_3(n, m, k, q);
        } else {
            tg_4(n, m, k, q);
        }
    } else {
        tg_2(n, m, q);
    }
}

Test details

Test 1 (public)

Group: 1, 3, 4

Verdict: ACCEPTED

input
`3 4 4 4 R 1 1 C 3 4 R 2 2 R 1 1` view save

correct output
`4 4 0 1` view save

user output
`4 4 0 1` view save

Test 2 (public)

Group: 3, 4

Verdict: ACCEPTED

input
`1000000000 1000000000 5 10 C 70724881 4 C 290904744 1 C 569311326 5 R 896293092 1 ...` view save

correct output
`3999999991 1999999998 19999999...` view save

user output
`3999999991 1999999998 19999999...` view save

Test 3

Group: 1, 3, 4

Verdict: ACCEPTED

input
`10 10 10 10 R 10 8 C 1 2 R 10 2 R 1 4 ...` view save

correct output
`0 13 0 8 7 20 0 0 10 7` view save

user output
`0 13 0 8 7 20 0 0 10 7` view save

Test 4

Group: 2, 4

Verdict: ACCEPTED

input
`1000000000 1000000000 1 200000 R 185082082 1 C 549662476 1 R 484749097 1 R 330334821 1 ...` view save

correct output
`199984000629575` view save

user output
`199984000629575` view save

Test 5

Group: 2, 4

Verdict: ACCEPTED

input
`1000000000 1000000000 1 200000 C 354072394 1 C 221236382 1 C 63527838 1 C 538599654 1 ...` view save

correct output
`126261014543986` view save

user output
`126261014543986` view save

Test 6

Group: 3, 4

Verdict: ACCEPTED

input
`1000000000 1000000000 2000 200...` view save

correct output
`999999400 2999997760 999999118...` view save

user output
`999999400 2999997760 999999118...` view save

Test 7

Group: 3, 4

Verdict: ACCEPTED

input
`1000000000 1000000000 2000 200...` view save

correct output
`999999481 0 999999445 0 0 0 0 ...` view save

user output
`999999481 0 999999445 0 0 0 0 ...` view save

Test 8

Group: 4

Verdict: WRONG ANSWER

input
`1000000000 1000000000 200000 2...` view save

correct output
`0 0 999997829 0 1999872519 199...` view save

user output
`0 0 999997829 0 1999872517 199...` view save

Feedback: Incorrect character on line 1 col 26: expected "1999872519", got "1999872517"

Test 9

Group: 4

Verdict: WRONG ANSWER

input
`1000000000 1000000000 200000 2...` view save

correct output
`999986843 0 0 999966411 999971...` view save

user output
`999986842 0 0 999966410 999971...` view save

Feedback: Incorrect character on line 1 col 9: expected "999986843", got "999986842"

Test 10

Group: 1, 3, 4

Verdict: ACCEPTED

input
`1 10 10 10 C 1 10 R 1 4 C 9 3 R 1 7 ...` view save

correct output
`1 0 0 0 0 0 0 9 0 0` view save

user output
`1 0 0 0 0 0 0 9 0 0` view save

Test 11

Group: 1, 3, 4

Verdict: ACCEPTED

input
`10 1 10 10 R 4 6 R 5 1 R 4 2 R 3 9 ...` view save

correct output
`0 0 0 0 0 0 0 10 0 0` view save

user output
`0 0 0 0 0 0 0 10 0 0` view save

Test 12

Group: 2, 4

Verdict: ACCEPTED

input
`1 1000000000 1 200000 C 298761159 1 R 1 1 C 831911362 1 C 25171734 1 ...` view save

correct output
`1000000000` view save

user output
`1000000000` view save

Test 13

Group: 2, 4

Verdict: ACCEPTED

input
`1000000000 1 1 200000 R 68306849 1 C 1 1 C 1 1 R 485427101 1 ...` view save

correct output
`1000000000` view save

user output
`1000000000` view save

Test 14

Group: 4

Verdict: WRONG ANSWER

input
`1000000000 1000000000 100 2000...` view save

correct output
`2003899199298 2016897879262 20...` view save

user output
`2003899198056 2016897877986 20...` view save

Feedback: Incorrect character on line 1 col 10: expected "2003899199298", got "2003899198056"

Test 15

Group: 4

Verdict: WRONG ANSWER

input
`1000000000 1000000000 100 2000...` view save

correct output
`1267960483393 1326958437362 12...` view save

user output
`1267960482131 1326958436045 12...` view save

Feedback: Incorrect character on line 1 col 10: expected "1267960483393", got "1267960482131"

Test 16

Group: 4

Verdict: WRONG ANSWER

input
`1000000000 1000000000 10000 20...` view save

correct output
`26998778013 13999380552 239989...` view save

user output
`26998777998 13999380545 239989...` view save

Feedback: Incorrect character on line 1 col 8: expected "26998778013", got "26998777998"

Test 17

Group: 4

Verdict: WRONG ANSWER

input
`1000000000 1000000000 10000 20...` view save

correct output
`7999699356 8999760379 12999665...` view save

user output
`7999699348 8999760370 12999665...` view save

Feedback: Incorrect character on line 1 col 9: expected "7999699356", got "7999699348"

Datatähti 2026 alku

Maalaus

Code

Test details

Test 1 (public)

Test 2 (public)

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Tasks

Submissions (wolruso)