QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#26044#2833. HamiltonHakujitsuAC ✓16ms7480kbC++2.0kb2022-04-05 23:40:412022-04-29 02:47:53

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-29 02:47:53]
  • Judged
  • Verdict: AC
  • Time: 16ms
  • Memory: 7480kb
  • [2022-04-05 23:40:41]
  • Submitted

answer

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

void debug_out() {cerr << endl;}
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T)
{
    cerr << " " << H;
    debug_out(T...);
}
#ifndef ONLINE_JUDGE
    #define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
#else
    #define debug(...) 42
#endif

int n;

void solve(){
    vector<string> mp(n);
    for (auto &s : mp) cin >> s;
    vector<int> res;
    for (int i = 0; i < n; i += 1) {
        if(res.empty()) {
            res.emplace_back(i);
            continue;
        }
        int zero = 0;
        int one = 0;
        for (int j = 1; j < res.size(); j += 1) {
            if(mp[res[j - 1]][res[j]] == '0') zero += 1;
            else one += 1;
        }
        if(zero == 0) {
            res.insert(res.begin(), i);
            continue;
        }
        if(one == 0) {
            res.emplace_back(i);
            continue;
        }
        int j = 0;
        for (; j + 1 < res.size(); j += 1) {
            if(mp[res[j]][res[j + 1]] == '1') {
                break;
            }
        }
        if(mp[res[j - 1]][i] == '0' || mp[res[j]][i] == '1') {
            res.insert(res.begin() + j, i);
            continue;
        }
        if(mp[res[j]][i] == '0' || mp[res[j + 1]][i] == '1'){
            res.insert(res.begin() + j + 1, i);
            continue;
        }
        assert(0);
    }
    
    for (int i = 0; i < n; i += 1) {
        if(mp[res[i]][res[(i + 1) % n]] == '1') {
            for (int j = i, cnt = 0; cnt < n; j = (j + 1) % n, cnt += 1) {
                cout << res[j] + 1 << " \n"[cnt == n - 1];
            }
            return;
        }
    }
    for (int i = 0; i < n; i += 1) {
        cout << res[i] + 1 << " \n"[i == n - 1];
    } 
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    while(cin >> n) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3668kb

input:

3
001
000
100
4
0000
0000
0000
0000

output:

1 3 2
2 1 3 4

result:

ok 2 cases.

Test #2:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

3
000
000
000
3
010
100
000
3
011
100
100
3
011
101
110

output:

2 1 3
2 1 3
2 1 3
3 2 1

result:

ok 4 cases.

Test #3:

score: 0
Accepted
time: 2ms
memory: 3708kb

input:

4
0000
0000
0000
0000
4
0000
0001
0000
0100
4
0100
1010
0100
0000
4
0111
1000
1000
1000
4
0010
0011
1101
0110
4
0111
1011
1100
1100
4
0111
1011
1101
1110
4
0000
0011
0101
0110
4
0101
1010
0100
1000
4
0011
0011
1100
1100
4
0010
0001
1000
0100

output:

2 1 3 4
4 2 1 3
3 2 1 4
2 1 3 4
4 3 2 1
3 2 1 4
4 3 2 1
3 4 2 1
3 2 1 4
2 4 1 3
2 1 4 3

result:

ok 11 cases.

Test #4:

score: 0
Accepted
time: 1ms
memory: 3568kb

input:

5
00000
00000
00000
00000
00000
5
00001
00000
00000
00000
10000
5
00010
00010
00000
11000
00000
5
00000
00001
00001
00001
01110
5
00001
00001
00001
00001
11110
5
00101
00100
11011
00100
10100
5
01111
10011
10000
11000
11000
5
00011
00011
00011
11101
11110
5
01101
10111
11001
01001
11110
5
00111
0011...

output:

2 1 3 4 5
2 1 3 4 5
2 1 3 4 5
4 5 2 1 3
4 5 2 1 3
5 1 3 2 4
4 2 1 3 5
1 5 3 4 2
4 5 3 2 1
5 2 4 1 3
5 4 3 2 1
5 4 2 1 3
3 5 4 2 1
5 3 4 2 1
5 1 3 2 4
5 3 4 2 1
4 3 2 1 5
5 3 2 1 4
2 4 1 3 5
2 5 4 1 3
5 4 2 1 3
1 5 3 4 2
1 3 2 4 5
1 3 2 4 5
2 5 4 1 3
4 5 3 2 1
4 5 2 1 3
3 5 2 1 4
5 4 1 3 2
5 3 4 2 1
...

result:

ok 34 cases.

Test #5:

score: 0
Accepted
time: 3ms
memory: 3572kb

input:

6
000000
000000
000000
000000
000000
000000
6
000000
000000
000001
000000
000000
001000
6
010000
100100
000000
010000
000000
000000
6
000100
000000
000100
101010
000100
000000
6
000100
000000
000100
101011
000100
000100
6
001000
001000
110111
001000
001000
001000
6
001100
000100
100100
111011
000100...

output:

2 1 3 4 5 6
2 1 3 4 5 6
4 2 1 3 5 6
3 4 2 1 5 6
3 4 2 1 5 6
1 3 2 4 5 6
2 4 1 3 5 6
5 3 4 2 1 6
4 3 2 1 5 6
4 5 1 3 2 6
1 5 4 3 2 6
6 5 4 3 2 1
5 6 4 3 2 1
5 4 3 2 1 6
6 5 4 3 2 1
6 5 4 3 2 1
2 6 1 5 3 4
6 3 2 1 5 4
6 5 2 4 1 3
3 2 1 4 5 6
4 3 2 1 5 6
6 5 3 2 1 4
6 3 2 1 5 4
6 5 4 3 2 1
4 6 5 3 2 1
...

result:

ok 156 cases.

Test #6:

score: 0
Accepted
time: 2ms
memory: 3568kb

input:

7
0000010
0001011
0001010
0110100
0001001
1110001
0100110
7
0101001
1011000
0101100
1110010
0010010
0001100
1000000
7
0001111
0011001
0100100
1100101
1011000
1000000
1101000
7
0111111
1011101
1101001
1110010
1100010
1001101
1110010
7
0010111
0010001
1101010
0010000
1000011
1010100
1100100
7
0001010
...

output:

5 7 6 3 4 2 1
5 6 4 3 2 1 7
7 4 5 2 1 3 6
5 6 4 3 2 1 7
6 5 1 3 2 4 7
6 3 4 2 1 5 7
5 7 6 4 2 1 3
2 1 3 4 5 6 7
2 4 1 3 5 6 7
6 7 2 1 3 5 4
7 1 5 3 4 2 6
4 7 3 6 5 2 1
1 3 2 4 5 6 7
7 4 1 3 2 5 6
6 5 4 1 3 2 7
6 3 2 1 4 5 7
7 3 2 5 4 6 1
7 3 4 2 1 6 5
6 7 5 2 4 1 3
3 2 4 5 1 6 7
7 2 1 3 4 5 6
6 7 2 ...

result:

ok 286 cases.

Test #7:

score: 0
Accepted
time: 3ms
memory: 3568kb

input:

5
01000
10100
01010
00100
00000
9
001101110
001010001
110100110
101010000
010100011
100000000
101000000
101010001
010010010
4
0000
0011
0101
0110
8
00100101
00101100
11000011
00001111
01010101
11011000
00110000
10111000
9
000000001
001101000
010000100
010000111
000000000
010000111
001101010
00010110...

output:

4 3 2 1 5
8 9 2 5 4 1 3 6 7
3 4 2 1
2 4 1 5 3 6 7 8
9 8 6 7 2 1 3 4 5
2 4 1 3
5 4 1 3 2 6
5 6 4 3 2 1
7 6 2 1 4 3 5
7 5 6 2 4 1 3
10 9 6 7 4 3 2 1 5 8
3 9 2 5 6 4 7 1 8 10
2 1 4 3 5 6
6 7 5 2 4 1 3 8
8 6 7 5 2 4 1 3 9
1 3 2
3 2 1
2 1 3 4 5 6
7 3 2 1 4 5 6
2 1 3
1 3 2
4 5 2 1 3
4 3 5 2 6 1
5 6 3 2 4 ...

result:

ok 322 cases.

Test #8:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

10
0010001000
0010011001
1101101001
0010111000
0011000110
0101001100
1111010001
0000110011
0000100101
0110001110
10
0000000010
0000001001
0000001101
0000100000
0001010111
0000101011
0110010100
0010101000
1000110000
0110110000
10
0110010111
1011111110
1100101010
0100001101
0110001111
1100001010
01111...

output:

9 10 2 4 1 6 5 7 8 3
9 5 8 2 1 3 6 4 7 10
10 5 3 2 1 4 6 8 9 7
10 3 6 4 5 2 1 7 8 9
10 8 9 4 7 6 3 5 2 1
4 8 7 6 5 2 1 3 9 10
10 5 2 1 3 4 6 7 8 9
7 10 9 8 6 5 2 1 3 4
9 10 5 6 2 1 3 4 7 8
10 5 3 2 1 6 7 4 8 9
10 8 9 3 7 4 6 5 2 1
9 6 1 3 2 4 7 5 8 10
10 7 9 8 2 6 4 5 1 3
6 10 8 9 4 3 2 1 5 7
10 9 8...

result:

ok 200 cases.

Test #9:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

10
0110101100
1010100111
1101100101
0010111010
1111001010
0001000000
1001100111
1110001001
0101101000
0110001100
10
0111110111
1001111100
1001100100
1110101111
1111001010
1100001000
0101110100
1111001010
1001100100
1001000000
10
0100000111
1011111001
0100001111
0100100110
0101011100
0100100110
01101...

output:

10 8 7 5 4 3 2 1 6 9
7 5 3 4 2 1 8 6 9 10
10 3 9 6 8 7 5 2 1 4
8 9 5 7 6 3 2 1 4 10
10 9 2 4 1 3 6 5 7 8
9 8 5 4 3 2 1 7 6 10
5 3 2 1 6 7 8 9 4 10
6 10 8 9 5 3 4 2 1 7
9 8 7 6 5 2 1 4 3 10
5 10 1 9 8 6 7 3 4 2
10 9 7 8 6 5 4 3 2 1
10 5 3 2 1 4 6 7 8 9
3 10 9 7 6 5 4 2 1 8
4 10 3 9 6 8 5 7 2 1
4 9 5 ...

result:

ok 200 cases.

Test #10:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

20
00011111000111100010
00100111111000000010
01011011101000100111
10100010000100000010
10100100000010101101
11001001010010000111
11110000010000111001
11100100111000010101
01100001011101100010
01000111100111011001
01100001100111111111
10010000111001010000
10001100011001001000
10000000111110111010
101...

output:

19 17 18 8 16 7 15 14 13 11 12 10 9 2 6 1 5 3 4 20
18 17 16 14 5 7 6 1 3 2 4 8 10 9 12 13 11 15 19
12 20 18 19 14 17 15 16 13 9 10 4 2 1 3 6 7 8 5 11 21 22
13 12 11 9 8 4 3 2 1 6 7 5 10
27 30 28 29 26 24 14 23 15 22 18 21 20 19 16 17 13 12 7 9 8 3 4 2 1 5 6 10 11 25
21 22 20 18 19 17 13 9 7 3 4 2 1 ...

result:

ok 72 cases.

Test #11:

score: 0
Accepted
time: 6ms
memory: 3536kb

input:

59
01110100011001000100111000110110010001011111001011011101100
10001011111001111100111111100010111011100101001100001000101
10000011101010011100111011000001101110001100001110110101001
10001100100110101001000000101101101110001110111001110001101
010101010101101111110011111000100101111111101001111100111...

output:

56 54 52 49 50 48 45 41 42 38 37 35 29 31 30 27 26 25 24 20 16 18 17 13 12 10 5 2 1 3 6 7 4 8 9 11 15 14 19 21 22 23 28 32 33 34 36 39 40 43 44 46 47 51 53 55 57 58 59
62 58 61 60 59 56 55 53 52 45 38 41 40 35 37 36 30 24 17 23 14 22 20 21 19 18 13 12 10 8 3 6 5 4 2 1 7 9 11 15 25 16 27 26 28 29 31 ...

result:

ok 29 cases.

Test #12:

score: 0
Accepted
time: 5ms
memory: 3608kb

input:

160
0010110100011110110110110001100110111000000100001100110101001011100101011100011100111011011011010011010110101100000011111010110111001011001100010000101111001101
000011011110000111010100011011010001001101001100111010101101001011001101001001000001011010001101100111011110110101111010101100000101001...

output:

160 155 159 158 157 156 151 149 122 148 147 138 146 143 145 144 139 142 140 141 124 137 125 136 131 135 134 132 133 130 128 129 127 126 121 115 114 93 112 94 111 98 110 109 108 99 107 102 106 100 105 103 104 101 97 96 95 90 89 87 81 86 85 78 84 83 82 67 64 65 63 56 61 59 60 57 54 55 51 52 29 28 26 2...

result:

ok 14 cases.

Test #13:

score: 0
Accepted
time: 2ms
memory: 3792kb

input:

438
01000100111101110010100101010001000101100011101011001001011110011100000110001001100101100101110011110111001101001101100111110010011001000110100110101001001101110001110011101010100010110100001011110011001000000001111111011001001010011101110010110111011111100011111101101001101010101010110000000111...

output:

438 437 431 432 429 430 427 428 416 413 412 410 411 404 405 402 400 391 398 397 394 396 395 393 392 390 389 380 388 387 386 381 385 383 384 382 377 372 376 360 375 373 374 361 359 357 355 356 354 352 342 351 349 350 348 346 347 345 339 338 337 335 334 331 332 330 329 321 323 322 315 314 307 302 303 ...

result:

ok 7 cases.

Test #14:

score: 0
Accepted
time: 9ms
memory: 4888kb

input:

1227
0100010000101001111110111010100100001100101111001011101010010000100111110110000001101101000101010011000101100110010011010100010011111000101101011001010111010010101001100100011000100000101011011011110101010011011110111101110010100010101111010101011001100001000110011101101010010011110010011011100...

output:

1216 1227 1217 1226 1225 1224 1219 1223 1218 1222 1220 1221 1214 1203 1202 1201 1200 1197 1199 1198 1194 1151 1191 1150 1190 1152 1189 1188 1187 1158 1186 1159 1185 1183 1184 1182 1178 1181 1179 1180 1162 1177 1167 1176 1175 1171 1174 1173 1172 1170 1168 1169 1166 1164 1165 1163 1160 1161 1154 1157 ...

result:

ok 2 cases.

Test #15:

score: 0
Accepted
time: 6ms
memory: 4708kb

input:

1078
0111011100111011000000110100010011001100100101011100111000110001110111110010111010110111010110001010100111101001110111010010000001000100110000000010000010111010101000000110101011011011000001100000011111010001010001101111011110111110000110111111111111101100110100011001110110111011111001110010110...

output:

1078 1076 1077 1074 1073 1072 1070 1071 1067 1066 1065 1062 1061 1060 1051 1052 1039 1048 1044 1047 1040 1046 1045 1038 1035 1036 1032 1024 1021 1019 1020 1015 1014 1000 1008 1001 1007 1003 1006 1005 1004 1002 999 998 997 992 996 995 994 993 988 985 971 976 966 975 974 973 972 970 967 969 968 965 96...

result:

ok 2 cases.

Test #16:

score: 0
Accepted
time: 7ms
memory: 5072kb

input:

1310
0110101010101111001001001110010101000100000000011001001110111010011000110110010000001110111100110100110110110000011001000101100100000011011111011100010001101111001100100000011100111111101101001011000101000011100101111011100101011111000100101110011110001101110110100111101101011000000000101000101...

output:

1310 1306 1309 1307 1308 1301 1304 1303 1302 1295 1284 1294 1292 1293 1291 1289 1290 1288 1285 1287 1286 1281 1282 1277 1280 1279 1278 1276 1273 1269 1272 1270 1271 1268 1265 1266 1262 1261 1257 1258 1255 1254 1244 1249 1247 1248 1246 1245 1241 1238 1236 1237 1234 1232 1229 1231 1230 1218 1227 1226 ...

result:

ok 2 cases.

Test #17:

score: 0
Accepted
time: 10ms
memory: 5860kb

input:

1542
0000100001001001100011001101100001110111010111001110111110011011001000110010001111000000100011101001000100000001111001110100110101101111000011100010000100000111010001010110101110000001000001110100101111100001110010111000111001010111011100100100111011010101001100100101110110011000001011001000011...

output:

1536 1542 1541 1535 1528 1525 1524 1523 1498 1496 1495 1492 1494 1493 1491 1479 1490 1489 1488 1477 1487 1481 1486 1482 1485 1483 1484 1480 1476 1456 1463 1462 1461 1457 1460 1459 1458 1450 1455 1454 1451 1453 1452 1447 1442 1445 1444 1437 1440 1439 1438 1434 1433 1429 1431 1430 1427 1425 1426 1422 ...

result:

ok 2 cases.

Test #18:

score: 0
Accepted
time: 14ms
memory: 7348kb

input:

2000
0101010000001001011001110100110110001010001110110101101100010010011100000111001100000000110111011111100001110001111011101101110010100100001001110010001111011110011011010000100001011100000000110011000110010100101010110100001010101001111101011001110011010001100110000110101110000001000101001101010...

output:

2000 1999 1997 1998 1995 1982 1994 1993 1983 1992 1991 1981 1990 1989 1987 1988 1986 1984 1985 1973 1974 1970 1972 1971 1965 1964 1961 1960 1959 1958 1952 1947 1945 1946 1944 1921 1941 1925 1940 1939 1938 1937 1923 1936 1935 1934 1932 1933 1928 1931 1930 1929 1927 1926 1924 1922 1920 1917 1916 1905 ...

result:

ok 1 cases.

Test #19:

score: 0
Accepted
time: 13ms
memory: 7368kb

input:

2000
0100001100010101000111011110110000001010100001111010011110111010011101000001100111011101101100000100100011001100011101011110101011101000010000000001010110001100011111100011010110101010001100011100011100000111011011100010110010100001111101011001010111111101011100111011110001101000111100110101000...

output:

2000 1998 1999 1992 1997 1996 1994 1995 1990 1989 1983 1982 1978 1975 1971 1974 1970 1973 1972 1965 1968 1966 1967 1954 1964 1963 1961 1962 1952 1953 1951 1949 1950 1946 1948 1947 1945 1940 1932 1938 1936 1937 1929 1908 1925 1924 1923 1921 1922 1918 1917 1916 1915 1910 1914 1912 1913 1911 1909 1906 ...

result:

ok 1 cases.

Test #20:

score: 0
Accepted
time: 6ms
memory: 7380kb

input:

2000
0110101010100011101110010101000111001011110000101111001110111111100111000101010001110111000110110001010000010101101001011001111111011111111111011111000011100001111110000101100100000110100100100110110010000101101101100100001101100010011100000011110000100100011110111001101001101100110111011101011...

output:

1998 1996 1982 1988 1983 1987 1984 1986 1985 1981 1979 1976 1970 1971 1967 1936 1964 1960 1963 1962 1961 1959 1958 1957 1956 1944 1955 1951 1954 1952 1953 1950 1949 1948 1947 1946 1945 1942 1943 1939 1941 1940 1937 1938 1884 1934 1933 1931 1932 1930 1923 1929 1927 1928 1926 1924 1925 1887 1922 1912 ...

result:

ok 1 cases.

Test #21:

score: 0
Accepted
time: 10ms
memory: 7448kb

input:

2000
0110000110000000010000010011101111110001110101010000000001101110101010101001111001010100100101001100010100101000110001000101000101010011011000000100011110100001000010000111100110111010110001000100011100100011111001011011111011111001101101111011111011111010011100001111010001011101110000000001011...

output:

1996 1997 1985 1994 1992 1993 1990 1991 1983 1984 1980 1972 1977 1976 1975 1974 1970 1969 1968 1966 1961 1965 1963 1964 1954 1955 1952 1948 1950 1949 1947 1943 1941 1942 1939 1937 1903 1936 1902 1935 1904 1934 1933 1932 1931 1930 1929 1913 1928 1914 1927 1920 1926 1924 1925 1922 1923 1921 1915 1919 ...

result:

ok 1 cases.

Test #22:

score: 0
Accepted
time: 11ms
memory: 7480kb

input:

2000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok 1 cases.

Test #23:

score: 0
Accepted
time: 16ms
memory: 7456kb

input:

2000
0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1990 1989 1988 1987 1986 1985 1984 1983 1982 1981 1980 1979 1978 1977 1976 1975 1974 1973 1972 1971 1970 1969 1968 1967 1966 1965 1964 1963 1962 1961 1960 1959 1958 1957 1956 1955 1954 1953 1952 1951 1950 1949 1948 1947 1946 1945 1944 1943 1942 1941 ...

result:

ok 1 cases.