Task: | Hiitism |
Sender: | Sold days |
Submission time: | 2024-11-16 15:29:28 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.01 s | details |
#7 | ACCEPTED | 0.01 s | details |
#8 | ACCEPTED | 0.03 s | details |
#9 | ACCEPTED | 0.03 s | details |
#10 | ACCEPTED | 0.04 s | details |
#11 | ACCEPTED | 0.04 s | details |
#12 | ACCEPTED | 0.02 s | details |
#13 | ACCEPTED | 0.01 s | details |
#14 | ACCEPTED | 0.01 s | details |
#15 | ACCEPTED | 0.01 s | details |
#16 | ACCEPTED | 0.02 s | details |
#17 | ACCEPTED | 0.02 s | details |
#18 | ACCEPTED | 0.01 s | details |
#19 | ACCEPTED | 0.01 s | details |
#20 | ACCEPTED | 0.01 s | details |
#21 | ACCEPTED | 0.01 s | details |
#22 | ACCEPTED | 0.01 s | details |
#23 | ACCEPTED | 0.01 s | details |
#24 | ACCEPTED | 0.01 s | details |
#25 | ACCEPTED | 0.01 s | details |
#26 | ACCEPTED | 0.01 s | details |
#27 | ACCEPTED | 0.01 s | details |
#28 | ACCEPTED | 0.01 s | details |
#29 | ACCEPTED | 0.01 s | details |
#30 | ACCEPTED | 0.01 s | details |
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 |