QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #375748 | #2833. Hamilton | schrodingerstom | AC ✓ | 9ms | 7912kb | C++14 | 3.0kb | 2024-04-03 15:28:54 | 2024-04-03 15:28:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
bool memBeg;
template<typename T,typename TT> void chkmin(T &x,TT y) {if(x>y) x=y;}
template<typename T,typename TT> void chkmax(T &x,TT y) {if(x<y) x=y;}
constexpr int mod=998244353;
void inc(int &x,int y) {x+=y; x-=(x>=mod)*mod;}
void dec(int &x,int y) {x-=y; x+=(x<0)*mod;}
constexpr int add(int x,int y) {return (x+y>=mod)?x+y-mod:x+y;}
constexpr int sub(int x,int y) {return (x<y)?x-y+mod:x-y;}
constexpr int quick_pow(int x,ll times,int ret=1) {
for(;times;times>>=1,x=1ll*x*x%mod) if(times&1) ret=1ll*ret*x%mod;
return ret;
}
constexpr int maxn=2005;
int n,ppre[maxn],pnxt[maxn];
char mat[maxn][maxn];
bool memEn;
void fl() {
freopen(".in","r",stdin);
freopen(".out","w",stdout);
}
int main() {
fprintf(stderr,"%.24lf\n",fabs(&memEn-&memBeg)/1024.0/1024.0);
// fl();
while(~scanf("%d",&n)) {
for(int i=1;i<=n;i++) scanf("%s",mat[i]+1);
memset(ppre,0,sizeof(int)*(n+2));
memset(pnxt,0,sizeof(int)*(n+2));
int tead=0,rail=n+1;
pnxt[tead]=1; ppre[rail]=2;
ppre[1]=tead; pnxt[1]=2;
ppre[2]=1; pnxt[2]=rail;
auto emplace=[&](int pos,int idx)->void {
ppre[idx]=ppre[pos]; pnxt[ppre[pos]]=idx;
pnxt[idx]=pos; ppre[pos]=idx;
};
int dif=-1;
for(int i=3;i<=n;i++) {
if(dif==-1) {
if(mat[pnxt[tead]][pnxt[pnxt[tead]]]==mat[ppre[rail]][i]) {
emplace(rail,i);
if(mat[ppre[ppre[rail]]][i]!=mat[i][pnxt[tead]]) dif=i;
} else if(mat[ppre[rail]][i]==mat[i][pnxt[tead]]) {
emplace(rail,i); dif=ppre[ppre[rail]];
} else {
emplace(pnxt[tead],i); dif=ppre[rail];
}
} else {
if(mat[ppre[dif]][dif]==mat[dif][i]) {
emplace(pnxt[dif],i);
if(mat[ppre[i]][i]!=mat[i][pnxt[i]]) {
dif=i;
} else dif=pnxt[i];
} else {
emplace(dif,i);
if(mat[ppre[i]][i]!=mat[i][pnxt[i]]) {
dif=i;
} else dif=ppre[i];
}
if(dif==pnxt[tead]&&mat[dif][pnxt[dif]]==mat[dif][ppre[rail]]) dif=-1;
if(dif==ppre[rail]&&mat[dif][pnxt[tead]]==mat[dif][ppre[dif]]) dif=-1;
if(dif==pnxt[tead]) dif=ppre[rail];
}
// for(int j=pnxt[tead];j!=rail;j=pnxt[j]) printf("%d ",j);
// puts("");
// for(int j=pnxt[tead];pnxt[j]!=rail;j=pnxt[j]) printf("%c ",mat[j][pnxt[j]]);
// printf("%c\n",mat[ppre[rail]][pnxt[tead]]);
// printf("dif = %d\n",dif);
}
for(int i=pnxt[tead];i!=rail;i=pnxt[i]) printf("%d ",i);
puts("");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3868kb
input:
3 001 000 100 4 0000 0000 0000 0000
output:
1 2 3 1 2 3 4
result:
ok 2 cases.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
3 000 000 000 3 010 100 000 3 011 100 100 3 011 101 110
output:
1 2 3 1 2 3 3 1 2 1 2 3
result:
ok 4 cases.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3936kb
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:
1 2 3 4 1 2 3 4 1 2 4 3 3 1 4 2 1 4 2 3 4 1 2 3 1 2 3 4 3 1 4 2 1 2 4 3 1 4 2 3 1 2 3 4
result:
ok 11 cases.
Test #4:
score: 0
Accepted
time: 0ms
memory: 3976kb
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:
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 5 1 2 3 4 1 2 3 4 5 1 2 4 5 3 3 1 2 5 4 1 2 5 3 4 1 2 3 5 4 1 4 2 3 5 1 2 3 4 5 3 1 2 4 5 3 1 2 4 5 3 1 2 4 5 3 1 5 4 2 3 1 2 4 5 1 2 3 4 5 1 2 3 5 4 1 2 5 4 3 1 2 5 4 3 1 2 3 5 4 3 5 1 4 2 1 2 4 5 3 1 2 4 5 3 1 4 5 2 3 1 2 4 5 3 5 1 2 3 4 1 2...
result:
ok 34 cases.
Test #5:
score: 0
Accepted
time: 1ms
memory: 3944kb
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:
1 2 3 4 5 6 1 2 3 4 5 6 1 6 2 5 4 3 1 2 3 5 6 4 1 2 3 5 6 4 1 2 4 5 6 3 1 2 5 6 4 3 1 2 5 6 3 4 1 2 3 6 5 4 1 2 6 5 4 3 1 5 4 2 3 6 1 2 3 4 5 6 1 2 3 5 6 4 6 1 2 3 4 5 1 2 3 4 5 6 1 2 3 4 5 6 3 6 1 5 4 2 1 2 3 6 4 5 5 1 4 2 3 6 4 1 2 3 6 5 5 1 2 3 6 4 4 1 2 3 5 6 1 2 3 5 6 4 1...
result:
ok 156 cases.
Test #6:
score: 0
Accepted
time: 1ms
memory: 3900kb
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:
7 4 1 2 3 5 6 1 2 3 4 6 7 5 3 5 1 4 2 7 6 5 1 2 3 4 6 7 1 2 4 7 5 6 3 3 1 5 6 7 4 2 3 1 2 6 7 5 4 3 1 4 5 2 6 7 1 2 5 4 6 7 3 1 2 3 5 4 7 6 3 1 2 6 7 5 4 1 2 5 4 6 3 7 1 2 4 3 5 6 7 1 2 3 4 5 6 7 3 1 4 5 7 6 2 4 1 2 3 7 6 5 1 5 4 2 3 6 7 5 3 1 7 2 6 4 1 4 2 3 5 7 6 1 5 4 2 3 6 7 ...
result:
ok 286 cases.
Test #7:
score: 0
Accepted
time: 1ms
memory: 3880kb
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:
1 2 3 5 4 1 2 6 5 7 4 9 8 3 3 1 4 2 1 2 4 3 5 7 6 8 3 1 4 5 9 8 7 6 2 1 4 2 3 1 2 3 5 6 4 1 2 6 3 5 4 4 1 2 6 7 5 3 1 4 2 3 5 6 7 5 1 2 3 7 6 8 4 9 10 1 2 5 6 4 7 3 8 10 9 1 2 6 5 3 4 1 5 6 2 7 8 4 3 9 1 5 2 4 3 7 6 8 1 2 3 1 2 3 1 6 5 4 2 3 1 2 7 6 5 4 3 1 2 3 1 2 3 3 1 4 5 2 ...
result:
ok 322 cases.
Test #8:
score: 0
Accepted
time: 1ms
memory: 3904kb
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:
1 2 5 7 10 9 8 6 4 3 5 1 2 3 4 8 9 7 10 6 1 2 3 9 10 7 8 6 5 4 1 2 3 7 6 8 5 9 10 4 1 4 5 9 10 8 7 6 2 3 1 5 6 7 10 8 9 4 2 3 3 1 10 9 8 7 6 5 4 2 3 1 2 4 6 7 10 9 8 5 3 1 4 6 7 8 9 10 5 2 1 2 7 10 9 8 5 6 4 3 3 6 1 5 4 9 10 8 2 7 1 2 3 4 5 8 9 10 7 6 1 6 10 7 9 8 2 5 4 3 1 2 3 8 10 9 7...
result:
ok 200 cases.
Test #9:
score: 0
Accepted
time: 1ms
memory: 3884kb
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:
1 2 3 4 5 7 10 9 8 6 3 1 2 4 5 7 8 10 9 6 1 2 4 5 7 8 6 9 3 10 4 1 2 6 10 9 7 8 5 3 1 4 2 9 10 8 7 3 6 5 1 2 3 4 5 7 8 10 9 6 4 1 2 3 10 5 9 8 7 6 1 2 4 3 5 9 8 10 6 7 4 1 2 5 6 7 8 10 9 3 6 3 5 1 4 7 8 2 10 9 7 1 2 3 4 5 6 8 9 10 4 1 2 3 10 9 8 7 6 5 3 1 2 4 5 6 7 8 9 10 1 2 3 6 7 10 9...
result:
ok 200 cases.
Test #10:
score: 0
Accepted
time: 1ms
memory: 4044kb
input:
20 00011111000111100010 00100111111000000010 01011011101000100111 10100010000100000010 10100100000010101101 11001001010010000111 11110000010000111001 11100100111000010101 01100001011101100010 01000111100111011001 01100001100111111111 10010000111001010000 10001100011001001000 10000000111110111010 101...
output:
3 1 2 4 6 7 18 19 20 5 17 16 15 14 13 10 12 11 9 8 1 2 4 5 6 3 7 8 19 9 18 17 16 12 15 14 13 10 11 3 1 2 4 8 9 13 16 17 18 19 14 20 15 21 7 22 12 10 11 6 5 1 2 5 6 13 11 12 10 9 8 7 4 3 4 1 2 5 6 7 10 11 14 13 15 16 24 25 23 27 30 28 29 26 22 18 21 20 19 17 12 9 8 3 1 13 2 12 9 11 10 8 4 7 6 5 ...
result:
ok 72 cases.
Test #11:
score: 0
Accepted
time: 1ms
memory: 4120kb
input:
59 01110100011001000100111000110110010001011111001011011101100 10001011111001111100111111100010111011100101001100001000101 10000011101010011100111011000001101110001100001110110101001 10001100100110101001000000101101101110001110111001110001101 010101010101101111110011111000100101111111101001111100111...
output:
3 1 4 5 8 21 25 26 27 30 35 49 50 57 59 58 56 48 55 54 53 52 51 47 46 45 44 43 42 36 41 40 38 39 37 31 34 33 32 29 28 24 23 22 20 7 19 18 11 17 12 16 13 15 14 9 10 6 2 1 2 4 12 18 17 19 21 20 23 24 22 37 40 51 52 53 55 59 60 61 58 63 62 57 56 54 50 47 49 48 46 39 45 41 44 43 42 38 36 25 35 34 28 33...
result:
ok 29 cases.
Test #12:
score: 0
Accepted
time: 1ms
memory: 4276kb
input:
160 0010110100011110110110110001100110111000000100001100110101001011100101011100011100111011011011010011010110101100000011111010110111001011001100010000101111001101 000011011110000111010100011011010001001101001100111010101101001011001101001001000001011010001101100111011110110101111010101100000101001...
output:
1 10 11 12 2 13 15 16 17 20 21 19 22 24 25 26 27 32 33 36 40 39 41 46 48 49 52 53 51 62 63 61 64 56 65 66 68 69 71 72 74 75 76 77 78 80 79 88 91 113 116 154 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...
result:
ok 14 cases.
Test #13:
score: 0
Accepted
time: 2ms
memory: 4780kb
input:
438 01000100111101110010100101010001000101100011101011001001011110011100000110001001100101100101110011110111001101001101100111110010011001000110100110101001001101110001110011101010100010110100001011110011001000000001111111011001001010011101110010110111011111100011111101101001101010101010110000000111...
output:
1 2 4 3 12 13 7 14 11 25 28 30 29 33 32 34 31 35 36 37 38 50 52 53 51 54 55 60 61 59 62 63 58 64 56 65 66 69 70 71 68 72 67 73 57 74 78 79 80 87 93 94 97 98 101 102 103 104 105 106 107 108 109 100 113 112 114 118 119 131 130 150 151 132 152 153 155 156 157 158 154 159 160 149 166 167 168 169 171 174...
result:
ok 7 cases.
Test #14:
score: 0
Accepted
time: 5ms
memory: 6644kb
input:
1227 0100010000101001111110111010100100001100101111001011101010010000100111110110000001101101000101010011000101100110010011010100010011111000101101011001010111010010101001100100011000100000101011011011110101010011011110111101110010100010101111010101011001100001000110011101101010010011110010011011100...
output:
1 2 5 11 14 16 17 15 18 21 25 26 28 31 33 34 38 39 40 41 43 44 45 42 46 37 68 70 71 72 73 75 74 76 69 81 80 85 86 82 87 84 88 83 94 93 95 106 107 97 108 110 111 109 112 113 114 105 115 116 104 117 118 119 100 120 121 103 122 124 125 126 138 145 146 148 149 150 147 151 152 153 144 154 155 160 164 165...
result:
ok 2 cases.
Test #15:
score: 0
Accepted
time: 5ms
memory: 6872kb
input:
1078 0111011100111011000000110100010011001100100101011100111000110001110111110010111010110111010110001010100111101001110111010010000001000100110000000010000010111010101000000110101011011011000001100000011111010001010001101111011110111110000110111111111111101100110100011001110110111011111001110010110...
output:
1 2 3 4 6 7 5 8 16 22 23 21 24 28 27 29 32 33 41 49 50 52 59 58 60 61 62 63 55 64 73 74 80 81 85 87 89 90 102 103 104 105 106 107 115 116 117 114 118 119 120 123 124 126 127 129 130 131 134 138 137 139 142 143 141 144 140 145 146 147 148 150 151 163 162 164 165 161 166 158 168 169 170 172 173 174 17...
result:
ok 2 cases.
Test #16:
score: 0
Accepted
time: 2ms
memory: 7364kb
input:
1310 0110101010101111001001001110010101000100000000011001001110111010011000110110010000001110111100110100110110110000011001000101100100000011011111011100010001101111001100100000011100111111101101001011000101000011100101111011100101011111000100101110011110001101110110100111101101011000000000101000101...
output:
1 2 3 7 8 6 13 14 9 15 12 18 20 24 29 30 31 33 34 32 38 39 40 37 41 36 42 43 35 46 47 66 68 69 73 77 76 79 84 88 87 92 93 94 95 89 97 98 96 99 106 107 108 109 110 114 115 113 117 118 120 119 122 124 125 126 127 129 130 131 128 132 123 136 137 138 145 148 150 155 159 158 160 164 163 165 166 162 167 1...
result:
ok 2 cases.
Test #17:
score: 0
Accepted
time: 3ms
memory: 7752kb
input:
1542 0000100001001001100011001101100001110111010111001110111110011011001000110010001111000000100011101001000100000001111001110100110101101111000011100010000100000111010001010110101110000001000001110100101111100001110010111000111001010111011100100100111011010101001100100101110110011000001011001000011...
output:
17 4 1 2 6 8 9 7 10 5 11 12 3 13 14 15 16 18 19 23 24 30 31 35 39 46 45 47 53 54 44 55 52 57 59 63 64 65 67 68 69 70 71 66 74 78 79 87 94 95 103 104 124 125 126 127 128 105 129 123 130 131 122 132 133 134 135 138 139 137 140 141 145 146 147 144 148 149 150 142 151 153 155 154 156 164 165 167 166 168...
result:
ok 2 cases.
Test #18:
score: 0
Accepted
time: 8ms
memory: 7868kb
input:
2000 0101010000001001011001110100110110001010001110110101101100010010011100000111001100000000110111011111100001110001111011101101110010100100001001110010001111011110011011010000100001011100000000110011000110010100101010110100001010101001111101011001110011010001100110000110101110000001000101001101010...
output:
1 2 4 7 15 16 11 17 18 14 20 21 23 24 31 32 35 36 37 39 40 45 44 46 38 49 48 51 52 53 50 54 61 74 75 76 77 79 81 82 80 83 92 93 94 98 97 100 102 103 106 105 116 115 117 118 111 121 122 120 123 129 130 132 134 135 136 133 137 138 139 142 141 143 147 146 148 149 145 150 151 152 144 153 140 154 131 162...
result:
ok 1 cases.
Test #19:
score: 0
Accepted
time: 3ms
memory: 7912kb
input:
2000 0100001100010101000111011110110000001010100001111010011110111010011101000001100111011101101100000100100011001100011101011110101011101000010000000001010110001100011111100011010110101010001100011100011100000111011011100010110010100001111101011001010111111101011100111011110001101000111100110101000...
output:
1 4 2 3 5 9 10 13 15 14 16 17 12 20 19 21 22 18 23 11 24 8 25 28 29 30 27 31 26 32 33 38 39 37 40 42 46 47 50 49 77 78 76 79 80 73 84 85 83 86 97 98 117 118 120 119 121 133 132 134 149 151 150 152 148 153 155 154 156 157 158 160 161 163 162 164 165 166 168 169 170 167 171 185 186 187 189 193 194 190...
result:
ok 1 cases.
Test #20:
score: 0
Accepted
time: 8ms
memory: 7812kb
input:
2000 0110101010100011101110010101000111001011110000101111001110111111100111000101010001110111000110110001010000010101101001011001111111011111111111011111000011100001111110000101100100000110100100100110110010000101101101100100001101100010011100000011110000100100011110111001101001101100110111011101011...
output:
3 1 2 4 5 6 7 9 12 13 11 23 25 26 30 29 35 36 37 38 39 43 44 40 45 47 48 51 58 57 59 61 62 63 64 66 65 67 75 76 78 79 80 77 81 74 82 83 73 84 72 100 101 102 99 103 104 85 107 108 111 113 116 118 122 124 130 131 135 136 137 138 139 140 141 144 150 151 146 152 153 154 149 158 169 168 172 173 177 178 1...
result:
ok 1 cases.
Test #21:
score: 0
Accepted
time: 8ms
memory: 7852kb
input:
2000 0110000110000000010000010011101111110001110101010000000001101110101010101001111001010100100101001100010100101000110001000101000101010011011000000100011110100001000010000111100110111010110001000100011100100011111001011011111011111001101101111011111011111010011100001111010001011101110000000001011...
output:
1 2 6 7 8 9 3 11 12 10 13 22 26 27 28 35 37 38 36 39 40 42 43 46 49 50 48 51 47 52 59 60 55 61 58 62 56 63 66 68 69 67 70 71 77 76 78 79 80 81 93 94 96 106 107 108 111 112 113 114 116 117 115 123 124 129 130 131 128 132 135 141 140 142 139 150 151 144 152 154 153 155 149 156 159 160 161 163 164 171 ...
result:
ok 1 cases.
Test #22:
score: 0
Accepted
time: 9ms
memory: 7868kb
input:
2000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
1 2 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: 3ms
memory: 7792kb
input:
2000 0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
1 2 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.