CSES - HIIT Open 2024 - Results
Submission details
Task:Hiitism
Sender:Tyämiesklubi
Submission time:2024-11-16 17:00:11 +0200
Language:C++ (C++20)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#20.00 sdetails
#30.00 sdetails
#40.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.01 sdetails
#80.14 sdetails
#90.17 sdetails
#100.19 sdetails
#110.18 sdetails
#12ACCEPTED0.04 sdetails
#13ACCEPTED0.01 sdetails
#14ACCEPTED0.01 sdetails
#15ACCEPTED0.01 sdetails
#160.03 sdetails
#170.03 sdetails
#18ACCEPTED0.03 sdetails
#19ACCEPTED0.03 sdetails
#20ACCEPTED0.02 sdetails
#21ACCEPTED0.01 sdetails
#22ACCEPTED0.01 sdetails
#23ACCEPTED0.01 sdetails
#24ACCEPTED0.01 sdetails
#25ACCEPTED0.03 sdetails
#26ACCEPTED0.03 sdetails
#27ACCEPTED0.03 sdetails
#28ACCEPTED0.03 sdetails
#290.01 sdetails
#300.01 sdetails

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<string> g(n);
for(string &i : g) cin >> i;
vector<int> c(1<<8, -1);
map<int, char> ic;
c['H'] = 0;
c['I'] = 1;
c['T'] = 2;
ic[0] = 'H';
ic[1] = 'I';
ic[2] = 'T';
set<int> htaken, wtaken;
vector<vector<int> > w(3, vector<int>(n)), h(3, vector<int>(m));
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(g[i][j] == '.') continue;
w[c[g[i][j]]][i]++;
h[c[g[i][j]]][j]++;
}
}
vector<tuple<char, int, char> > ans;
while(true){
int d = -1, j = -1, cc = -1;
for(int i=0; i<n; i++){
for(int k=0; k<3; k++){
if(w[k][i] >= n && wtaken.find(i) == wtaken.end()){
d = 0;
j = i;
cc = k;
break;
}
}
if(d != -1) break;
}
if(d == -1){
for(int i=0; i<m; i++){
for(int k=0; k<3; k++){
if(h[k][i] >= m && htaken.find(i) == htaken.end()){
d = 1;
j = i;
cc = k;
break;
}
}
if(d != -1) break;
}
}
if(d == -1) break;
if(d == 0){
for(int i=0; i<m; i++){
if(c[g[j][i]] != cc) continue;
for(int k=0; k<3; k++){
if(k != cc){
w[k][j]++;
h[k][i]++;
}
}
g[j][i] = '*';
}
wtaken.insert(j);
ans.push_back({'R', j+1, ic[cc]});
} else {
for(int i=0; i<n; i++){
if(c[g[i][j]] != cc) continue;
for(int k=0; k<3; k++){
if(k != cc){
w[k][i]++;
h[k][j]++;
}
}
g[i][j] = '*';
}
htaken.insert(j);
ans.push_back({'C', j+1, ic[cc]});
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(g[i][j] != '.' && g[i][j] != '*'){
cout << "Impossible\n";
return 0;
}
}
}
reverse(ans.begin(), ans.end());
for(auto [a, b, c] : ans){
cout << a << ' ' << b << ' ' << c << '\n';
}
}

Test details

Test 1

Verdict:

input
3 3
.H.
IHI
TTT

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

user output
R 2 I
C 2 H
R 3 T

Test 2

Verdict:

input
2 2
.H
IH

correct output
2
R 2 I
C 2 H

user output
R 2 I
C 2 H

Test 3

Verdict:

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
C 3 T
R 10 I
R 4 I
C 5 H
C 4 I
...

Test 4

Verdict:

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

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

user output
R 3 T
C 44 H
R 34 I
C 30 T
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:

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
C 886 H
C 822 I
C 83 T
C 55 I
R 984 H
...

Test 9

Verdict:

input
1000 1000
HHHHHHHHHHHHHHHHHHHHHIHHHHHHHH...

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

user output
R 500 I
C 938 H
R 263 H
C 888 I
C 804 H
...

Test 10

Verdict:

input
1000 1000
TITTTHTITTHTHTHITTTTTTTHTHTTTI...

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

user output
C 22 H
R 531 T
C 412 H
C 288 H
R 227 H
...

Test 11

Verdict:

input
1000 1000
IHHTTTTHTIIIHTTTTHTIITTTHHITIT...

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

user output
R 200 H
C 445 I
C 355 I
C 303 I
R 167 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:

input
1000 500
HIHHTHTITTHIHTHTTHIHTTIHTTHHTH...

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

user output
Impossible

Test 17

Verdict:

input
500 1000
IHIIIHIIHIIIIIHIHHIIIIIIIIIIII...

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

user output
Impossible

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:

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

correct output
0

user output
(empty)

Test 30

Verdict:

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

correct output
1
C 562 T

user output
C 562 T