QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#56371 | #2833. Hamilton | YaoBIG# | AC ✓ | 19ms | 8100kb | C++ | 1.7kb | 2022-10-18 23:15:55 | 2022-10-18 23:15:57 |
Judging History
answer
#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
using namespace std;
void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(H h, T... t) {
cerr << " " << to_string(h);
debug_out(t...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: "; debug_out(__VA_ARGS__)
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n;
while (cin >> n) {
vector<string> ss(n);
for (auto &s: ss) cin >> s;
vi vec{0, 1};
rep(v, 2, n - 1) {
int found = -1;
rep(i, 0, sz(vec) - 1) {
int a = vec[(i - 1 + sz(vec)) % sz(vec)];
int b = vec[i];
int c = vec[(i + 1) % sz(vec)];
if (ss[a][b] == '0' && ss[b][c] == '1') {
found = i;
break;
}
}
if (found == -1) vec.insert(vec.begin(), v);
else {
int a = vec[found];
if (ss[v][a] == '0') vec.insert(vec.begin() + found + 1, v);
else vec.insert(vec.begin() + found, v);
}
}
int found = -1;
rep(i, 0, sz(vec) - 1) {
int a = vec[(i - 1 + sz(vec)) % sz(vec)];
int b = vec[i];
int c = vec[(i + 1) % sz(vec)];
if (ss[a][b] == '0' && ss[b][c] == '1') {
found = i;
break;
}
}
if (found != -1) rotate(vec.begin(), vec.begin() + found, vec.end());
for (auto x: vec) printf("%d ", x + 1);
puts("");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3784kb
input:
3 001 000 100 4 0000 0000 0000 0000
output:
3 1 2 4 3 1 2
result:
ok 2 cases.
Test #2:
score: 0
Accepted
time: 2ms
memory: 3684kb
input:
3 000 000 000 3 010 100 000 3 011 100 100 3 011 101 110
output:
3 1 2 1 2 3 3 1 2 3 1 2
result:
ok 4 cases.
Test #3:
score: 0
Accepted
time: 2ms
memory: 3800kb
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:
4 3 1 2 2 4 3 1 2 3 1 4 4 1 2 3 4 2 3 1 3 1 2 4 4 3 1 2 4 2 3 1 4 1 2 3 3 1 4 2 3 4 1 2
result:
ok 11 cases.
Test #4:
score: 0
Accepted
time: 1ms
memory: 3700kb
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:
5 4 3 1 2 5 4 3 1 2 4 3 1 2 5 2 5 4 3 1 2 5 4 3 1 5 3 1 2 4 5 1 2 3 4 1 5 2 4 3 4 5 3 1 2 5 3 1 4 2 5 4 3 1 2 5 4 1 2 3 4 5 1 2 3 5 4 3 1 2 3 1 2 4 5 5 3 1 2 4 3 1 2 4 5 5 3 1 2 4 4 3 1 2 5 2 5 4 3 1 2 5 4 3 1 3 5 1 4 2 3 1 2 4 5 5 3 1 2 4 5 4 1 2 3 1 5 4 2 3 5 2 4 3 1 5 3...
result:
ok 34 cases.
Test #5:
score: 0
Accepted
time: 2ms
memory: 3792kb
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:
6 5 4 3 1 2 6 5 4 3 1 2 6 3 1 4 5 2 4 3 1 2 5 6 6 4 3 1 2 5 6 3 1 2 4 5 6 4 3 1 2 5 6 4 3 1 2 5 6 3 1 2 4 5 6 5 4 3 1 2 6 3 1 5 4 2 6 5 4 2 3 1 5 6 4 3 1 2 5 4 3 1 2 6 6 5 4 3 1 2 6 5 4 3 1 2 3 6 1 5 4 2 6 3 1 2 5 4 5 6 3 1 4 2 3 1 2 4 5 6 3 1 2 5 4 6 6 5 3 1 2 4 6 5 3 1 2 4 6...
result:
ok 156 cases.
Test #6:
score: 0
Accepted
time: 2ms
memory: 3704kb
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:
4 7 3 1 2 5 6 5 3 4 1 2 6 7 5 1 4 2 6 3 7 5 6 4 3 1 2 7 7 5 6 3 1 2 4 4 2 3 1 5 6 7 6 7 5 4 3 1 2 7 3 1 4 5 2 6 7 3 1 2 5 4 6 7 4 6 3 1 2 5 7 5 4 3 1 2 6 7 6 4 5 2 3 1 6 3 5 1 2 4 7 3 4 5 6 7 1 2 5 4 3 1 2 6 7 3 1 2 4 5 6 7 6 5 3 4 1 2 7 6 7 3 1 2 5 4 6 7 5 3 1 4 2 4 1 2 3 5 6 7 ...
result:
ok 286 cases.
Test #7:
score: 0
Accepted
time: 2ms
memory: 3640kb
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:
3 1 4 2 5 9 8 3 1 2 6 5 7 4 4 2 3 1 8 4 6 3 5 1 2 7 9 8 7 6 2 3 1 4 5 3 1 4 2 6 4 1 2 3 5 5 6 3 1 4 2 7 6 1 2 4 3 5 7 6 5 3 1 4 2 9 10 7 3 4 1 2 6 5 8 10 9 5 6 4 7 3 8 1 2 6 1 2 4 3 5 4 3 1 5 6 2 7 8 9 6 4 3 1 5 2 8 7 2 3 1 3 1 2 6 1 2 3 4 5 7 2 3 1 4 5 6 1 2 3 2 3 1 3 5 4 1 2 ...
result:
ok 322 cases.
Test #8:
score: 0
Accepted
time: 2ms
memory: 3776kb
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:
7 10 9 8 6 4 3 1 2 5 10 6 5 4 3 1 2 8 9 7 10 9 3 1 2 4 5 6 8 7 1 5 2 4 3 7 6 8 9 10 10 8 7 6 2 3 1 4 5 9 10 7 6 5 1 2 3 4 9 8 1 2 3 4 5 6 7 8 9 10 7 10 9 8 5 3 1 2 4 6 9 10 5 2 3 1 4 6 7 8 10 7 8 6 3 5 4 1 2 9 1 10 7 9 8 6 2 3 4 5 7 2 6 3 4 5 1 8 9 10 6 10 7 9 8 2 5 4 3 1 10 8 3 1 4 2 5...
result:
ok 200 cases.
Test #9:
score: 0
Accepted
time: 3ms
memory: 3756kb
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 7 5 4 3 1 2 6 8 9 5 4 3 1 2 8 6 9 7 10 3 10 1 9 6 8 7 5 4 2 10 9 8 6 2 4 3 5 1 7 4 2 6 5 7 3 8 9 1 10 8 7 4 1 2 5 3 6 9 10 10 3 1 2 6 7 8 4 9 5 10 9 7 8 6 3 1 4 5 2 10 2 9 7 8 4 3 5 1 6 2 10 9 6 3 4 1 5 7 8 6 10 9 8 7 5 2 3 1 4 10 3 1 2 4 5 6 7 8 9 3 10 9 8 7 6 5 4 1 2 9 8 5 3 4 1 2 ...
result:
ok 200 cases.
Test #10:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
20 00011111000111100010 00100111111000000010 01011011101000100111 10100010000100000010 10100100000010101101 11001001010010000111 11110000010000111001 11100100111000010101 01100001011101100010 01000111100111011001 01100001100111111111 10010000111001010000 10001100011001001000 10000000111110111010 101...
output:
20 5 17 16 15 14 13 10 12 11 9 8 3 1 2 4 6 7 18 19 18 17 16 12 15 14 13 10 3 7 8 9 1 2 4 5 6 11 19 22 7 21 15 20 14 19 18 17 16 13 9 8 4 5 1 2 3 6 11 10 12 13 11 12 10 9 8 7 4 3 1 2 5 6 27 30 28 29 26 22 18 21 20 19 17 12 9 8 3 1 2 5 6 7 4 10 11 14 13 15 16 24 25 23 21 22 18 19 17 16 14 15 9 6 ...
result:
ok 72 cases.
Test #11:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
59 01110100011001000100111000110110010001011111001011011101100 10001011111001111100111111100010111011100101001100001000101 10000011101010011100111011000001101110001100001110110101001 10001100100110101001000000101101101110001110111001110001101 010101010101101111110011111000100101111111101001111100111...
output:
59 57 50 49 35 30 27 26 25 21 8 5 4 1 2 3 6 10 9 14 15 13 16 12 17 11 18 19 7 20 22 23 24 28 29 32 33 34 31 37 39 38 40 41 36 42 43 44 45 46 47 51 52 53 54 55 48 56 58 58 61 60 59 55 53 52 51 40 37 22 24 23 20 21 19 17 18 12 1 5 4 2 3 7 6 8 9 10 11 14 15 13 16 26 27 29 30 31 32 33 28 34 35 25 36 38...
result:
ok 29 cases.
Test #12:
score: 0
Accepted
time: 5ms
memory: 3732kb
input:
160 0010110100011110110110110001100110111000000100001100110101001011100101011100011100111011011011010011010110101100000011111010110111001011001100010000101111001101 000011011110000111010100011011010001001101001100111010101101001011001101001001000001011010001101100111011110110101111010101100000101001...
output:
160 155 159 158 157 156 153 115 152 117 151 119 150 120 149 118 148 137 147 138 146 143 145 144 139 142 140 141 122 136 131 135 134 132 133 124 130 125 129 128 123 127 126 121 114 93 112 94 111 98 110 107 109 108 99 106 100 105 104 103 102 101 97 95 96 92 90 89 87 81 86 85 84 83 82 73 70 67 60 59 58...
result:
ok 14 cases.
Test #13:
score: 0
Accepted
time: 2ms
memory: 3992kb
input:
438 01000100111101110010100101010001000101100011101011001001011110011100000110001001100101100101110011110111001101001101100111110010011001000110100110101001001101110001110011101010100010110100001011110011001000000001111111011001001010011101110010110111011111100011111101101001101010101010110000000111...
output:
438 428 437 436 426 391 406 399 405 404 403 400 402 401 398 397 394 396 395 393 392 390 389 380 388 387 386 381 385 383 384 382 377 375 376 374 373 372 369 371 370 368 365 345 364 354 363 362 359 361 360 357 358 356 355 348 353 351 352 350 349 347 346 344 340 341 338 337 332 330 329 320 326 325 298 ...
result:
ok 7 cases.
Test #14:
score: 0
Accepted
time: 12ms
memory: 5364kb
input:
1227 0100010000101001111110111010100100001100101111001011101010010000100111110110000001101101000101010011000101100110010011010100010011111000101101011001010111010010101001100100011000100000101011011011110101010011011110111101110010100010101111010101011001100001000110011101101010010011110010011011100...
output:
1225 1212 1224 1219 1223 1218 1222 1220 1221 1213 1217 1215 1216 1214 1211 1201 1200 1178 1180 1179 1176 1175 1171 1174 1173 1172 1147 1154 1150 1153 1151 1152 1139 1137 1138 1135 1128 1134 1131 1133 1132 1126 1124 1119 1123 1120 1122 1121 1116 1113 1115 1114 1108 1105 1102 1104 1103 1101 1100 1099 ...
result:
ok 2 cases.
Test #15:
score: 0
Accepted
time: 15ms
memory: 4960kb
input:
1078 0111011100111011000000110100010011001100100101011100111000110001110111110010111010110111010110001010100111101001110111010010000001000100110000000010000010111010101000000110101011011011000001100000011111010001010001101111011110111110000110111111111111101100110100011001110110111011111001110010110...
output:
1078 1076 1073 1072 1071 1070 1066 1065 1061 1062 1058 1057 1051 1048 1046 1045 1044 1043 1032 1036 1035 1024 1023 1017 1019 1018 1015 1012 1014 1013 1008 1006 1005 1004 1003 990 997 996 995 994 993 988 987 985 986 982 975 974 973 972 970 967 969 968 964 963 962 959 961 960 958 951 947 944 946 945 9...
result:
ok 2 cases.
Test #16:
score: 0
Accepted
time: 4ms
memory: 5568kb
input:
1310 0110101010101111001001001110010101000100000000011001001110111010011000110110010000001110111100110100110110110000011001000101100100000011011111011100010001101111001100100000011100111111101101001011000101000011100101111011100101011111000100101110011110001101110110100111101101011000000000101000101...
output:
1310 1306 1309 1308 1307 1304 1303 1302 1295 1294 1292 1293 1291 1288 1290 1289 1286 1281 1280 1279 1278 1273 1274 1270 1265 1266 1262 1261 1257 1254 1238 1237 1236 1232 1229 1231 1230 1227 1221 1218 1219 1216 1213 1211 1210 1208 1209 1207 1198 1206 1201 1205 1204 1202 1203 1200 1199 1190 1187 1172 ...
result:
ok 2 cases.
Test #17:
score: 0
Accepted
time: 7ms
memory: 6260kb
input:
1542 0000100001001001100011001101100001110111010111001110111110011011001000110010001111000000100011101001000100000001111001110100110101101111000011100010000100000111010001010110101110000001000001110100101111100001110010111000111001010111011100100100111011010101001100100101110110011000001011001000011...
output:
1542 1541 1504 1501 1486 1498 1497 1496 1490 1489 1488 1487 1485 1483 1484 1476 1468 1462 1461 1457 1460 1459 1458 1450 1455 1444 1454 1451 1453 1452 1443 1436 1442 1441 1440 1439 1431 1438 1437 1430 1427 1426 1425 1423 1422 1414 1419 1415 1418 1408 1417 1416 1404 1406 1405 1402 1403 1395 1399 1397 ...
result:
ok 2 cases.
Test #18:
score: 0
Accepted
time: 16ms
memory: 7984kb
input:
2000 0101010000001001011001110100110110001010001110110101101100010010011100000111001100000000110111011111100001110001111011101101110010100100001001110010001111011110011011010000100001011100000000110011000110010100101010110100001010101001111101011001110011010001100110000110101110000001000101001101010...
output:
2000 1999 1997 1998 1995 1982 1994 1993 1983 1992 1991 1981 1990 1986 1989 1987 1988 1984 1985 1973 1972 1971 1965 1964 1961 1960 1959 1958 1946 1939 1937 1938 1935 1934 1928 1933 1932 1931 1930 1929 1915 1926 1925 1924 1904 1923 1918 1922 1921 1919 1920 1917 1916 1913 1903 1912 1909 1911 1910 1906 ...
result:
ok 1 cases.
Test #19:
score: 0
Accepted
time: 11ms
memory: 8056kb
input:
2000 0100001100010101000111011110110000001010100001111010011110111010011101000001100111011101101100000100100011001100011101011110101011101000010000000001010110001100011111100011010110101010001100011100011100000111011011100010110010100001111101011001010111111101011100111011110001101000111100110101000...
output:
2000 1998 1999 1996 1994 1995 1986 1983 1982 1977 1975 1967 1969 1968 1964 1963 1962 1961 1960 1948 1954 1951 1953 1952 1949 1950 1945 1942 1935 1907 1925 1924 1923 1908 1922 1919 1921 1920 1918 1917 1916 1915 1914 1912 1913 1911 1909 1910 1904 1887 1886 1884 1876 1870 1853 1858 1855 1857 1856 1854 ...
result:
ok 1 cases.
Test #20:
score: 0
Accepted
time: 11ms
memory: 8100kb
input:
2000 0110101010100011101110010101000111001011110000101111001110111111100111000101010001110111000110110001010000010101101001011001111111011111111111011111000011100001111110000101100100000110100100100110110010000101101101100100001101100010011100000011110000100100011110111001101001101100110111011101011...
output:
1989 2000 1995 1999 1994 1998 1996 1997 1991 1993 1992 1987 1985 1986 1973 1965 1972 1971 1968 1970 1969 1967 1966 1964 1960 1963 1962 1961 1959 1958 1957 1956 1944 1955 1951 1954 1952 1953 1950 1949 1948 1947 1946 1945 1943 1942 1941 1940 1938 1933 1925 1924 1921 1920 1906 1905 1901 1904 1903 1900 ...
result:
ok 1 cases.
Test #21:
score: 0
Accepted
time: 11ms
memory: 8072kb
input:
2000 0110000110000000010000010011101111110001110101010000000001101110101010101001111001010100100101001100010100101000110001000101000101010011011000000100011110100001000010000111100110111010110001000100011100100011111001011011111011111001101101111011111011111010011100001111010001011101110000000001011...
output:
1997 1994 1989 1992 1991 1990 1975 1974 1973 1971 1965 1970 1969 1968 1967 1966 1964 1963 1953 1952 1950 1949 1940 1937 1939 1938 1927 1935 1934 1933 1928 1932 1931 1930 1929 1924 1923 1922 1919 1918 1917 1910 1912 1911 1909 1908 1907 1905 1906 1903 1901 1900 1899 1896 1895 1894 1892 1886 1885 1882 ...
result:
ok 1 cases.
Test #22:
score: 0
Accepted
time: 9ms
memory: 7984kb
input:
2000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
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.
Test #23:
score: 0
Accepted
time: 19ms
memory: 8048kb
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.