CSES - HIIT Open 2024 - Results
Submission details
Task:Hiitism
Sender:Sold days
Submission time:2024-11-16 15:29:28 +0200
Language:C++ (C++17)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.01 sdetails
#8ACCEPTED0.03 sdetails
#9ACCEPTED0.03 sdetails
#10ACCEPTED0.04 sdetails
#11ACCEPTED0.04 sdetails
#12ACCEPTED0.02 sdetails
#13ACCEPTED0.01 sdetails
#14ACCEPTED0.01 sdetails
#15ACCEPTED0.01 sdetails
#16ACCEPTED0.02 sdetails
#17ACCEPTED0.02 sdetails
#18ACCEPTED0.01 sdetails
#19ACCEPTED0.01 sdetails
#20ACCEPTED0.01 sdetails
#21ACCEPTED0.01 sdetails
#22ACCEPTED0.01 sdetails
#23ACCEPTED0.01 sdetails
#24ACCEPTED0.01 sdetails
#25ACCEPTED0.01 sdetails
#26ACCEPTED0.01 sdetails
#27ACCEPTED0.01 sdetails
#28ACCEPTED0.01 sdetails
#29ACCEPTED0.01 sdetails
#30ACCEPTED0.01 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int i = 0; i < rc[k].size(); i ++) {
      |                         ~~^~~~~~~~~~~~~~
input/code.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int j = 0; j < rc[1 - k].size(); j ++) {
      |                         ~~^~~~~~~~~~~~~~~~~~
input/code.cpp:127:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for (int j = 0; j < rc[1 - k].size(); j ++) {
      |                         ~~^~~~~~~~~~~~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;

struct info {
    int h, i, t;
    bool colored = true;
};


bool oneNonZero(info inf) {
    return (
        (inf.h != 0 && inf.i == 0 && inf.t == 0) || 
        (inf.h == 0 && inf.i != 0 && inf.t == 0) || 
        (inf.h == 0 && inf.i == 0 && inf.t != 0) 
    );
}

bool isBrushable(info inf) {
    return oneNonZero(inf) && inf.colored;
}

char getColor(info inf) {
    assert(oneNonZero(inf));
    // assumes oneNonZero
    if (inf.h != 0) return 'H';
    if (inf.i != 0) return 'I';
    if (inf.t != 0) return 'T';
    assert(false); // should never happpen
}

struct ans {
    int k;
    int i;
    char color;
};


int main()
{

    ios::sync_with_stdio(false);
    cin.tie(0);

    
    int n, m; cin >> n >> m;
    vector <string> input(n);
    for (int i = 0; i < n; i ++) {
        cin >> input[i];
    }

    
    // fill rows and cols
    vector <vector <info>> rc(2);
    rc[0].resize(n); // rows
    rc[1].resize(m); // cols

    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            if (input[i][j] == 'H') {
                rc[0][i].h ++;
                rc[1][j].h ++;
            } else if (input[i][j] == 'I') {
                rc[0][i].i ++;
                rc[1][j].i ++;
            } else if (input[i][j] == 'T') {
                rc[0][i].t ++;
                rc[1][j].t ++;
            } else if (input[i][j] == '.') {
                rc[0][i].colored = rc[1][j].colored = false;
            }
        }
    }
    

    vector <pair <int, int>> toBrush; // available for brushing

    // initial fill
    for (int k = 0; k < 2; k ++) {
        for (int i = 0; i < rc[k].size(); i ++) {
            if (isBrushable(rc[k][i])) {
                toBrush.emplace_back(k, i);
                rc[k][i].colored = false; // dont consider it anymore
            }
        }
    }

    vector <ans> answer;
    // processing
    while (!toBrush.empty()) {
        pair<int, int> cur = toBrush.back();
        int k = cur.first, i = cur.second;
        toBrush.pop_back();
        info el = rc[k][i];
        if (!oneNonZero(el)) {
            continue;  // all ?, ignore
        }

        // add it to answer
        answer.push_back(ans{k, i, getColor(el)});

        // relax others
        for (int j = 0; j < rc[1 - k].size(); j ++) {
            char c;
            if (k == 0) {
                c = input[i][j];
            } else {
                c = input[j][i];
            }

            if (c == 'H') {
                rc[1 - k][j].h --;
            } else if (c == 'I') {
                rc[1 - k][j].i --;
            } else if (c == 'T') {
                rc[1 - k][j].t --;
            }

            // now we may need to add it into the toBrush; duplicates are not added as they are marked as not colored
            if (isBrushable(rc[1 - k][j])) {
                toBrush.emplace_back(1 - k, j);
                // mark that we do not consider it anymore
                rc[1 - k][j].colored = false;
            }
        }

        // set the row or col to ? to check later
        for (int j = 0; j < rc[1 - k].size(); j ++) {
            if (k == 0) {
                input[i][j] = '?';
            } else {
                input[j][i] = '?';
            }
        }
    }

    // now check that everything is processed (. or ?)
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            if (input[i][j] != '.' && input[i][j] != '?') {
                cout << "Impossible";
                return 0;
            }
        }
    }


    // and now print the answer
    cout << answer.size() << '\n';
    reverse(answer.begin(), answer.end());
    for (auto a : answer) {
        if (a.k == 0) {
            cout << "R ";
        } else {
            cout << "C ";
        }

        cout << a.i + 1 << ' ' << a.color << '\n';
    }
}

Test details

Test 1

Verdict: ACCEPTED

input
3 3
.H.
IHI
TTT

correct output
3
R 2 I
C 2 H
R 3 T

user output
3
R 2 I
C 2 H
R 3 T

Test 2

Verdict: ACCEPTED

input
2 2
.H
IH

correct output
2
R 2 I
C 2 H

user output
2
R 2 I
C 2 H

Test 3

Verdict: ACCEPTED

input
10 10
T.TIH.....
IIIIIIIIII
T.TIH.....
TIIIHIIIII
...

correct output
7
C 3 T
R 10 I
R 4 I
C 5 H
...

user output
7
C 3 T
R 4 I
R 10 I
C 1 T
...

Test 4

Verdict: ACCEPTED

input
100 100
.............H........I.....IT...

correct output
19
R 3 T
C 44 H
R 34 I
C 30 T
...

user output
19
R 3 T
C 44 H
R 34 I
R 70 T
...

Test 5

Verdict: ACCEPTED

input
100 100
.........................H.......

correct output
Impossible

user output
Impossible

Test 6

Verdict: ACCEPTED

input
1000 1000
H.II..T.I.IH..I..H.I..I..ITHH....

correct output
Impossible

user output
Impossible

Test 7

Verdict: ACCEPTED

input
1000 1000
HHHIHHHHHHHHHHHHIHHHHHHHHHHHHH...

correct output
Impossible

user output
Impossible

Test 8

Verdict: ACCEPTED

input
1000 1000
IHIHTI.T.H..IHHIIT.I.TT.HH.HI....

correct output
1552
C 822 I
C 83 T
C 55 I
R 984 H
...

user output
1552
C 55 I
C 83 T
C 822 I
R 837 H
...

Test 9

Verdict: ACCEPTED

input
1000 1000
HHHHHHHHHHHHHHHHHHHHHIHHHHHHHH...

correct output
1727
R 500 I
C 938 H
C 804 H
R 263 H
...

user output
1727
R 500 I
C 804 H
C 938 H
R 413 I
...

Test 10

Verdict: ACCEPTED

input
1000 1000
TITTTHTITTHTHTHITTTTTTTHTHTTTI...

correct output
1856
C 22 H
R 531 T
C 412 H
C 288 H
...

user output
1856
R 227 H
C 63 T
C 22 H
R 531 T
...

Test 11

Verdict: ACCEPTED

input
1000 1000
IHHTTTTHTIIIHTTTTHTIITTTHHITIT...

correct output
1826
R 200 H
R 167 I
C 445 I
C 355 I
...

user output
1826
R 200 H
C 303 I
C 355 I
C 445 I
...

Test 12

Verdict: ACCEPTED

input
1000 1000
TTTTTITTTHTHTITIIHTIITIHTTIHTT...

correct output
Impossible

user output
Impossible

Test 13

Verdict: ACCEPTED

input
1000 1000
TITHITITIITTIIIIIHIIIIHTIIIHTI...

correct output
Impossible

user output
Impossible

Test 14

Verdict: ACCEPTED

input
1000 1000
TTTTTTTTTTTTTTTTTTTITTTTTTTITT...

correct output
Impossible

user output
Impossible

Test 15

Verdict: ACCEPTED

input
1000 1000
IHTHHHIHIIIHHTTHHHHIHIIHHIHHHH...

correct output
Impossible

user output
Impossible

Test 16

Verdict: ACCEPTED

input
1000 500
HIHHTHTITTHIHTHTTHIHTTIHTTHHTH...

correct output
1417
C 75 I
R 430 T
C 195 H
R 441 I
...

user output
1417
C 75 I
R 430 T
C 195 H
R 441 I
...

Test 17

Verdict: ACCEPTED

input
500 1000
IHIIIHIIHIIIIIHIHHIIIIIIIIIIII...

correct output
1418
C 971 T
C 744 I
C 654 I
C 540 T
...

user output
1418
C 140 H
C 16 T
C 197 T
C 255 T
...

Test 18

Verdict: ACCEPTED

input
1000 500
IIIIIIIIIIIIIIITIIIIIIITTIIIII...

correct output
Impossible

user output
Impossible

Test 19

Verdict: ACCEPTED

input
500 1000
HIITITHHHHIHHIHHTHIIIHHHHTHTHH...

correct output
Impossible

user output
Impossible

Test 20

Verdict: ACCEPTED

input
1000 1000
TIITIIIIIIIIIIIIIIIIIHIHIIIIII...

correct output
Impossible

user output
Impossible

Test 21

Verdict: ACCEPTED

input
1000 1000
TTHTTTTTHTTTHTTTTTTTTHHTTTTTIT...

correct output
Impossible

user output
Impossible

Test 22

Verdict: ACCEPTED

input
1000 1000
IHIIIIITHIIIHIHHHITHIIIIHTTIHI...

correct output
Impossible

user output
Impossible

Test 23

Verdict: ACCEPTED

input
1000 1000
TTHIHIITHTI.HHIHHITIHIHIHIITIH...

correct output
Impossible

user output
Impossible

Test 24

Verdict: ACCEPTED

input
1000 1000
IHIHIIIIIIIIIHIIIHIHIITIHIIIII...

correct output
Impossible

user output
Impossible

Test 25

Verdict: ACCEPTED

input
1000 500
HIHITTIHITHHHTITHIHHHTHHIHHIII...

correct output
Impossible

user output
Impossible

Test 26

Verdict: ACCEPTED

input
500 1000
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...

correct output
Impossible

user output
Impossible

Test 27

Verdict: ACCEPTED

input
1000 500
TTTTIHTTTHTTHTITTTTHTHTTHTITTI...

correct output
Impossible

user output
Impossible

Test 28

Verdict: ACCEPTED

input
500 1000
HTIIIHIIIHITIHIIIIIIHTIIIIITHI...

correct output
Impossible

user output
Impossible

Test 29

Verdict: ACCEPTED

input
1000 1000
.................................

correct output
0

user output
0

Test 30

Verdict: ACCEPTED

input
1000 1000
.................................

correct output
1
C 562 T

user output
1
C 562 T