Task: | Hiitism |
Sender: | Tyämiesklubi |
Submission time: | 2024-11-16 16:25:33 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | TIME LIMIT EXCEEDED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.01 s | details |
#4 | ACCEPTED | 0.01 s | details |
#5 | ACCEPTED | 0.01 s | details |
#6 | ACCEPTED | 0.20 s | details |
#7 | ACCEPTED | 0.37 s | details |
#8 | TIME LIMIT EXCEEDED | -- | details |
#9 | TIME LIMIT EXCEEDED | -- | details |
#10 | TIME LIMIT EXCEEDED | -- | details |
#11 | TIME LIMIT EXCEEDED | -- | details |
#12 | TIME LIMIT EXCEEDED | -- | details |
#13 | ACCEPTED | 0.61 s | details |
#14 | ACCEPTED | 0.56 s | details |
#15 | ACCEPTED | 0.45 s | details |
#16 | TIME LIMIT EXCEEDED | -- | details |
#17 | ACCEPTED | 0.93 s | details |
#18 | ACCEPTED | 0.18 s | details |
#19 | ACCEPTED | 0.18 s | details |
#20 | ACCEPTED | 0.95 s | details |
#21 | ACCEPTED | 0.50 s | details |
#22 | ACCEPTED | 0.55 s | details |
#23 | ACCEPTED | 0.58 s | details |
#24 | ACCEPTED | 0.45 s | details |
#25 | ACCEPTED | 0.39 s | details |
#26 | ACCEPTED | 0.61 s | details |
#27 | ACCEPTED | 0.19 s | details |
#28 | ACCEPTED | 0.17 s | details |
#29 | ACCEPTED | 0.01 s | details |
#30 | ACCEPTED | 0.01 s | details |
Code
#include <bits/stdc++.h>using namespace std;bool add(map<int, int> &s, int i, int len) {if (s.empty()) {s.insert({i, i});return len == 1;}auto n = s.lower_bound(i);if (n == s.end()) {auto p = prev(n);if (p->first <= i && i <= p->second) {return false;}if (i == p->second + 1) {++p->second;return p->first == 0 && p->second == len - 1;} else {s.insert({i, i});return len == 1;}}if (i == n->first) {return false;}if (i == n->first - 1) {if (n != s.begin()) {auto p = prev(n);if (i == p->second + 1) {p->second = n->second;s.erase(n);return p->first == 0 && p->second == len - 1;}}pair<int, int> updated = {n->first - 1, n->second};s.insert(updated);s.erase(n);return updated.first == 0 && updated.second == len - 1;}if (n == s.begin()) {s.insert({i, i});return len == 1;}auto p = prev(n);if (p->first <= i && i <= p->second) {return false;}if (i == p->second + 1) {++p->second;if (p->second >= n->first) {p->second = n->second;s.erase(n);}return p->first == 0 && p->second == len - 1;} else {s.insert({i, i});return len == 1;}}int toind(char c) {return c == 'H' ? 0 : c == 'I' ? 1 : c == 'T' ? 2 : -1;}int main() {ios::sync_with_stdio(0);cin.tie(0);int n, m;cin >> n >> m;char painting[1000][1000];map<int, int> rs[3][1000];map<int, int> cs[3][1000];bool hr[1000] = {};bool hc[1000] = {};queue<pair<int, int>> fr;queue<pair<int, int>> fc;vector<tuple<bool, int, int>> res;for (int r = 0; r < n; ++r) {string row;cin >> row;for (int c = 0; c < m; ++c) {char ch = row[c];painting[r][c] = ch;int ind = toind(ch);if (ind < 0) continue;if (add(rs[ind][r], c, m)) {fr.push({r, ind});}if (add(cs[ind][c], r, n)) {fc.push({c, ind});}}}while (true) {if (fr.empty() && fc.empty()) {break;}if (!fr.empty()) {auto row = fr.front();fr.pop();if (hr[row.first]) {continue;}res.push_back({false, row.first, row.second});hr[row.first] = true;for (int ind = 0; ind < 3; ++ind) {for (int c = 0; c < m; ++c) {if (add(cs[ind][c], row.first, n)) {fc.push({c, ind});}}}}if (!fc.empty()) {auto col = fc.front();fc.pop();if (hc[col.first]) {continue;}res.push_back({true, col.first, col.second});hc[col.first] = true;for (int ind = 0; ind < 3; ++ind) {for (int r = 0; r < n; ++r) {if (add(rs[ind][r], col.first, m)) {fr.push({r, ind});}}}}}for (int r = 0; r < n; ++r) {for (int c = 0; c < m; ++c) {if (painting[r][c] != '.') {if (!hr[r] && !hc[c]) {cout << "Impossible\n";return 0;}}}}cout << res.size() << '\n';for (int i = res.size() - 1; i >= 0; --i) {char rc = get<0>(res[i]) ? 'C' : 'R';int ind = get<2>(res[i]);char ind_c = ind == 0 ? 'H' : ind == 1 ? 'I' : 'T';cout << rc << ' ' << (get<1>(res[i]) + 1) << ' ' << ind_c << '\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 10 I R 4 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: TIME LIMIT EXCEEDED
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 |
---|
(empty) |
Test 9
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1000 HHHHHHHHHHHHHHHHHHHHHIHHHHHHHH... |
correct output |
---|
1727 R 500 I C 938 H C 804 H R 263 H ... |
user output |
---|
(empty) |
Test 10
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1000 TITTTHTITTHTHTHITTTTTTTHTHTTTI... |
correct output |
---|
1856 C 22 H R 531 T C 412 H C 288 H ... |
user output |
---|
(empty) |
Test 11
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1000 IHHTTTTHTIIIHTTTTHTIITTTHHITIT... |
correct output |
---|
1826 R 200 H R 167 I C 445 I C 355 I ... |
user output |
---|
(empty) |
Test 12
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1000 TTTTTITTTHTHTITIIHTIITIHTTIHTT... |
correct output |
---|
Impossible |
user output |
---|
(empty) |
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: TIME LIMIT EXCEEDED
input |
---|
1000 500 HIHHTHTITTHIHTHTTHIHTTIHTTHHTH... |
correct output |
---|
1417 C 75 I R 430 T C 195 H R 441 I ... |
user output |
---|
(empty) |
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 971 T C 540 T C 392 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 |