QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#314539 | #1193. Ambiguous Encoding | OFforest_1273 | AC ✓ | 4ms | 8156kb | C++14 | 1.6kb | 2024-01-25 19:56:39 | 2024-01-25 19:56:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef genshin
#include <experimental/iterator>
#endif
const int INF = 0x3F3F3F3F;
const int maxn = 16;
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> Q;
int dis[maxn + 1][1 << maxn];
signed main() { ios::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
vector<pair<int, int>> num(n+1); // len, mask
for(int i=1;i<=n;++i){
string s;cin>>s;
int x=0,len=0;
for(char c:s)x|=(c&1)<<len,++len;
num[i]={s.size(),x};
}
memset(dis, 0x3f, sizeof dis);
for(int i=1;i<=n;++i)/*初始化*/
for(int j=1;j<=n;++j){
int len1=num[i].first,len2=num[j].first,val1=num[i].second,val2=num[j].second;
if((len1==len2&&val1==val2)||len1<len2)continue;
if((val1&((1<<len2)-1))!=val2)continue;
int nxt_len=len1-len2,nxt_val=val1>>len2;
if(dis[nxt_len][nxt_val]>len1)dis[nxt_len][nxt_val]=len1,Q.push({len1,nxt_len,nxt_val});
}
while(!Q.empty()){
auto [d,len,val]=Q.top();Q.pop();
if(d>dis[len][val])continue;
for(int i=1;i<=n;++i){
int len2=num[i].first,val2=num[i].second,nxt_len,nxt_val,flag=0;
if(len>=len2&&((val&((1<<len2)-1))==val2))nxt_len=len-len2,nxt_val=val>>len2,flag=1;
else if(len<len2&&(val2&((1<<len)-1))==val)nxt_len=len2-len,nxt_val=val2>>len,flag=1;
if(!flag)continue;
int cost=max(0,len2-len);
if(d+cost<dis[nxt_len][nxt_val])dis[nxt_len][nxt_val]=d+cost,Q.push({d+cost,nxt_len,nxt_val});
}
}
if (dis[0][0] == INF)
cout << "0\n";
else
cout << dis[0][0] << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 8132kb
input:
3 0 01 10
output:
3
result:
ok answer is '3'
Test #2:
score: 0
Accepted
time: 2ms
memory: 7920kb
input:
3 00 01 1
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 2ms
memory: 7952kb
input:
3 00 10 1
output:
0
result:
ok answer is '0'
Test #4:
score: 0
Accepted
time: 2ms
memory: 7948kb
input:
10 1001 1011 01000 00011 01011 1010 00100 10011 11110 0110
output:
13
result:
ok answer is '13'
Test #5:
score: 0
Accepted
time: 0ms
memory: 7936kb
input:
3 1101 1 10
output:
4
result:
ok answer is '4'
Test #6:
score: 0
Accepted
time: 2ms
memory: 8136kb
input:
100 1010011110001 00000100010101 011010100100001 11100001100011 10010001010 1110001110110011 01001100111 1010100110010100 00000100111010 100111001100101 0010000000010 0111110011100110 0100111000001 1100101111110001 1100100110001 10100011010 10100000011000 1111001111001110 000000000101011 10101111011...
output:
102
result:
ok answer is '102'
Test #7:
score: 0
Accepted
time: 2ms
memory: 7940kb
input:
10 0110 001100 0100 0001 100 001010 0010 100010 1100 11101
output:
10
result:
ok answer is '10'
Test #8:
score: 0
Accepted
time: 0ms
memory: 7932kb
input:
10 1001 10111 11011 00010 001 001100 110 01110 111101 11100
output:
10
result:
ok answer is '10'
Test #9:
score: 0
Accepted
time: 2ms
memory: 7936kb
input:
10 0001 0101 1001 101 0010 010 00000 1000 00001 111101
output:
10
result:
ok answer is '10'
Test #10:
score: 0
Accepted
time: 1ms
memory: 8100kb
input:
100 0100001001101111 00001000100011 001111100110101 1010001010001 01110010101011 1110101100011 00100000100110 01111110100 110001111010 10101010001 00010000100100 00010011100 01101001100010 010111010101 00101110101001 00110100110110 00111001101 0001110011000011 11101100110 101111001011001 00101110100...
output:
110
result:
ok answer is '110'
Test #11:
score: 0
Accepted
time: 0ms
memory: 7868kb
input:
100 010110000010110 111001111001 00000010100111 1011000100011100 1010110100001000 0101110010110 11101010001 0001101001001101 10011111110010 01010001101 11011101010 011011111011001 111000111110 01011100011 0000111110110 000110001011 110100011000 10010011011 0011001010001 1010001110000110 100100100001...
output:
113
result:
ok answer is '113'
Test #12:
score: 0
Accepted
time: 2ms
memory: 7920kb
input:
10 011 011000 111011 0101 101000 010100 1101 10100 11111 001001
output:
11
result:
ok answer is '11'
Test #13:
score: 0
Accepted
time: 2ms
memory: 7924kb
input:
10 101 110 00000 100011 010 110001 001001 1110 011111 01001
output:
11
result:
ok answer is '11'
Test #14:
score: 0
Accepted
time: 0ms
memory: 7884kb
input:
200 100101110111000 0111100000111 1010110010001110 000001000000 111000100101 111010000110100 11100110010100 100110111110 1000100110110 0100010010111 001100010101 100001001110100 1110000011001111 0110100100100 111111111110 1110111010110 1101101000111 0001101001110001 000010110111110 101100110010 1010...
output:
116
result:
ok answer is '116'
Test #15:
score: 0
Accepted
time: 2ms
memory: 7948kb
input:
5 1 01 10101010101 10111000000 10000000101
output:
11
result:
ok answer is '11'
Test #16:
score: 0
Accepted
time: 0ms
memory: 7864kb
input:
100 000010101110 10101111011110 10000000001 001101011110101 110001010100 11110111011 0101101111010001 101010001101011 100001110100 100010110011000 1000001001101001 0011100110101 011110111100010 0100101100010 10001101011 011110010101011 0011001001000 0100001010100 11110110011 011101001011 01101011011...
output:
118
result:
ok answer is '118'
Test #17:
score: 0
Accepted
time: 2ms
memory: 7924kb
input:
10 01100 100 00101 0100 1110 11101 1010 01001 000101 10101
output:
12
result:
ok answer is '12'
Test #18:
score: 0
Accepted
time: 4ms
memory: 7912kb
input:
500 0110100111 10110100011100 100011111010111 010010111 0011100001101 10011001101101 0110010011 0101100 1000010111011 01110010110 111001111000 0110100010101 011001100100101 001000110001100 110100000101 100101100101111 0101111111110 00101001000010 1101100 0110000000 00011100000 1110010101 00000100010...
output:
14
result:
ok answer is '14'
Test #19:
score: 0
Accepted
time: 2ms
memory: 7880kb
input:
200 01100101110110 001100111001 1011000110000 101010101010 001000111100010 0010001111110011 010001010101000 010001001001000 1110100000100100 10001011011011 10001000010000 101101001101101 1100010011001001 10010100010100 00001001000111 0100000010011000 111000010100 000101001010000 000100100110101 0010...
output:
145
result:
ok answer is '145'
Test #20:
score: 0
Accepted
time: 2ms
memory: 7860kb
input:
10 1000 00001 01011 001001 110010 11000 110 01010 000001 01100
output:
14
result:
ok answer is '14'
Test #21:
score: 0
Accepted
time: 2ms
memory: 7856kb
input:
10 10111 1100 11011 001 0101 001000 00101 11101 100000 0111
output:
14
result:
ok answer is '14'
Test #22:
score: 0
Accepted
time: 0ms
memory: 7932kb
input:
200 1010111001101110 01010011010100 0111000011011 10000110011100 110110111010100 100001111010001 1110001100001 10001000011101 0001000110011010 1111110000000000 1001000110111001 101011110110111 1101011100010 100001000110 000001011001 011001111111 111101111101000 11101011100010 001011010101000 0001001...
output:
156
result:
ok answer is '156'
Test #23:
score: 0
Accepted
time: 0ms
memory: 8132kb
input:
10 1010 011010 010001 0101 001001 101000 011 111 10010 110
output:
17
result:
ok answer is '17'
Test #24:
score: 0
Accepted
time: 2ms
memory: 7864kb
input:
200 1111100000000 0011100001011100 00000000000111 1100101001111 100100010110111 11001111101011 1100101101101001 100001101010110 01001111000100 001111111001011 011111010101 0011000101010 0110010000000111 110101000110 1110101110011011 1101110010011 0010111101011010 1111010011010 11001000110001 0010010...
output:
188
result:
ok answer is '188'
Test #25:
score: 0
Accepted
time: 0ms
memory: 8136kb
input:
10 000 110100 0111 010 101 11100 010100 00110 011000 010111
output:
18
result:
ok answer is '18'
Test #26:
score: 0
Accepted
time: 0ms
memory: 7952kb
input:
200 1110101101 10111111001 1000011110 1111110011011 01100100101110 010001111000110 1010111010 1000110011010000 11100011110001 11000100001 1011101110011000 000110110000010 111111011000011 0110010000001 10001000101 1101010000 1000000001 1101000010000 01110101110 00000101111 0100111011110 0110110011011...
output:
0
result:
ok answer is '0'
Test #27:
score: 0
Accepted
time: 2ms
memory: 7928kb
input:
200 101010110010 1001001001000111 0010011011011101 1111100000111110 11101010011 10100001001001 000100000000 010011000001011 1100010110010011 11101101110 110001010001 00000111000 011010101001001 10011110110111 0111001111000 110111111010011 1000000110000101 01100101110 00011100011 0111001001111011 101...
output:
0
result:
ok answer is '0'
Test #28:
score: 0
Accepted
time: 0ms
memory: 7976kb
input:
1000 01000110 11101111 0100011000101111 0010111110011101 1001110111010001 1101000101110010 0111001000110101 0011010110001010 1000101011101011 1110101110111110 1011111001111101 0111110111110100 1111010001111100 0111110001000001 0100000100101010 0010101011010100 1101010001000010 0100001010010011 10010...
output:
2048
result:
ok answer is '2048'
Test #29:
score: 0
Accepted
time: 2ms
memory: 8136kb
input:
200 11001100000000 1010101001010 0111110011100010 111011011001000 0110111110010 111010010100010 0100111000001010 0001110101000010 00000100001101 01110010111001 000001100110000 1111011001000 10001110101100 111000011010110 10110110010001 11000101111010 1100000010011 000011010000001 11111011011110 1100...
output:
231
result:
ok answer is '231'
Test #30:
score: 0
Accepted
time: 2ms
memory: 8144kb
input:
200 10100110111100 101000100111101 0110111110110000 111110000001110 1001011001111101 001111001101111 00111101101111 01010100000100 111001100000001 1100001111011001 0110101010001 001101000011101 0000101111000101 11100110101010 00011111011001 1001010000111 000111100111110 0111111101001 011000101111001...
output:
283
result:
ok answer is '283'
Test #31:
score: 0
Accepted
time: 2ms
memory: 8144kb
input:
200 111101000110010 01001010110010 100010011011010 0101101110000 00101000111011 1010111110101 01111010011110 100011111110000 10000011100111 0111000010000111 001001011000011 0000100110011000 11100011110001 10111110110000 001100110100011 1101111011011 000100111100111 10010011100010 0011001010011 00001...
output:
350
result:
ok answer is '350'
Test #32:
score: 0
Accepted
time: 2ms
memory: 7864kb
input:
200 11000010000111 11110111011011 00100011011100 1101000001011 01100001110101 000111101010111 1011110100001011 0011110000011 0100011011001 01000101000000 00111111110110 111100011010001 100101111001100 1011101110111 1110110010000 1001011010001 1010111100001001 110001010111000 1011100001000 1010010001...
output:
359
result:
ok answer is '359'
Test #33:
score: 0
Accepted
time: 0ms
memory: 7880kb
input:
100 01101111110001 101000110111 11111011011 00000011010 0000101010001 010001100110 1110010000101 100101100011000 01100000100 1101111010011010 101110101100 101001110101001 00000011110 01000011010 011100110101111 10011010110 000000101100110 10100100011110 001010101001100 11111110000 10001001101010 100...
output:
36
result:
ok answer is '36'
Test #34:
score: 0
Accepted
time: 2ms
memory: 7888kb
input:
200 0111100011111000 0100111110000 010111111011111 1011011000001111 00100111001000 10111000101110 0110010001000011 01010011001011 11010011111110 0110010000010110 0101100001011 011011011100100 0011101110010110 1110010000001 001111010111110 1110011010100 111001000000111 001000100100001 1010101101110 1...
output:
367
result:
ok answer is '367'
Test #35:
score: 0
Accepted
time: 0ms
memory: 8108kb
input:
100 000001010010010 00100000011 0011001000001101 1011110011001 111010010100010 011001000100000 000101100001 110110100111 0011100011111111 1110010111010 10111001011111 101010011001 1011100100101101 0110001000110000 111010100010 010000111110 10010100011 01000011001000 1010101100101 000111111111 011001...
output:
37
result:
ok answer is '37'
Test #36:
score: 0
Accepted
time: 0ms
memory: 7924kb
input:
100 1011001001010101 000010011000001 1101101010101 110111101101 01110100100000 11111101010 0001010011011 111101110110001 110000100110011 111101110111 0100001101010 011101100111000 1001100001101000 1001100000000 11100011100 10100110110110 0011000110110000 1111111010010100 10001001001 0000001100001110...
output:
38
result:
ok answer is '38'
Test #37:
score: 0
Accepted
time: 2ms
memory: 7820kb
input:
200 00100010100101 011111101101000 0010100111101111 001101100000001 1111111001111 1101111110001 000000100010100 11100010110101 011011011001110 00000111010101 1100110110100101 0100010110011 1101011000111011 111000111100110 111010100001010 1011010001100001 0000110011000 1011101100101110 10111001101001...
output:
391
result:
ok answer is '391'
Test #38:
score: 0
Accepted
time: 0ms
memory: 7920kb
input:
100 0011010101100 0111110100111 11001110010 111011111111100 001000010110110 00010010000 1001010011110 100101101110 0010100110001000 1110100001101000 111111110101001 10000010011010 11111110001101 1000000110011101 111011000001100 00110101101 110101110001 0001110001101001 000000111001 1111100101000 010...
output:
39
result:
ok answer is '39'
Test #39:
score: 0
Accepted
time: 0ms
memory: 7892kb
input:
200 00000000110010 1010111101010 010101010110101 01011010001111 011000101010001 11111011001101 1110001100000 110110111111110 0000010110001 1011011111101000 1010010011010 0111111011001101 0101110110111010 1100110101010 0000100100110100 010110010100010 1001011111011 1110011001100 1111101001101 1010110...
output:
421
result:
ok answer is '421'
Test #40:
score: 0
Accepted
time: 2ms
memory: 7964kb
input:
200 100001111000011 11100101100101 101001101110011 0100000001010000 011010000100010 010000110001110 00011110001001 000111010011001 0010000010101 0010110011011 0101111010111 0100010011100100 101010000111011 01100110010101 1111000000110011 01101010000111 010000001001011 0011101101011 10000110110100 11...
output:
445
result:
ok answer is '445'
Test #41:
score: 0
Accepted
time: 0ms
memory: 7864kb
input:
100 0100100110110101 101000011011 111011000101000 11111001000 1101011111111 0000010011010110 10100001110 01111000100 101101011011000 1110011110100110 1100101111010110 10011011000011 0010111001110101 1001010111110110 11000110001100 00011010111100 111011000111 010000010111 11111111100000 1010011100110...
output:
47
result:
ok answer is '47'
Test #42:
score: 0
Accepted
time: 0ms
memory: 7928kb
input:
100 1111000001010 1000011001010 001011111010 010101100100 1111000101101001 101010011100 1100010000010111 11100011001100 1011111100011100 000001100000 00101111101 001010111010 0001010110101100 0010011110100010 111100000000111 010000100101 001011000010101 001110001000 011101001101000 000001110000010 0...
output:
48
result:
ok answer is '48'
Test #43:
score: 0
Accepted
time: 1ms
memory: 8156kb
input:
100 00101001011 1010000111111 01101101010101 110001101010000 00000011101010 0010100101101111 01101101010011 11111001111 0101001000011111 1101000001101 010011001001011 01001101011111 10010111101110 110101001110001 100010011000 000101101010 0000111010111 11110011010 10010101110 001001110111011 0101010...
output:
49
result:
ok answer is '49'
Test #44:
score: 0
Accepted
time: 0ms
memory: 7868kb
input:
500 101011100001100 0001100110110110 0001111101110000 11010000110111 110110001011110 011011011001011 101001011101001 1001111010100 10001101110110 00110001000011 1011110011100 001010000110011 01100110011110 01000111010011 01100010010001 0110000110101 01001010111001 00001100010010 0001110010111001 110...
output:
0
result:
ok answer is '0'
Test #45:
score: 0
Accepted
time: 2ms
memory: 7928kb
input:
100 10101111001 000010111001 10001000001 01101000011100 0001001101100011 00000011110 10010111011 01011001011 011111101101001 0000000000000 101100010111 0010111100110011 1101101110110011 0001010011100000 110010111011 1110110010000010 11010111010111 10001000011 0010101110110100 000100111001110 1100111...
output:
51
result:
ok answer is '51'
Test #46:
score: 0
Accepted
time: 2ms
memory: 8072kb
input:
100 111111001011 011011000011 1100010001000000 10110101001 0011000100100 0100000101010000 0000110110001 10110001011 01100011110 010010110111 00110001110 0100000110100 111101111111111 10000111010 110100110001011 0111011101001 010000010001 01011101110101 1000101100101 10000110111 001100011001110 01000...
output:
52
result:
ok answer is '52'
Test #47:
score: 0
Accepted
time: 2ms
memory: 7952kb
input:
100 10111101000100 11000000100 010111000100000 11011010101 0000000101100001 111100001111000 01010001001 11001011011 1101001110010001 0010100111110101 1001011110110 01010111010 011010101111 0100000010011 100001110111011 101110111100010 11001001000 000000011101110 1011100010110010 0001101011011 110011...
output:
54
result:
ok answer is '54'
Test #48:
score: 0
Accepted
time: 2ms
memory: 7868kb
input:
100 1100100101000 01011000111010 010101101011000 1010011101110111 1010010011011000 11001001010101 00010011010 110110001001101 10011111110111 10101110000 1010110001111 0110010100000100 100100100001 011101000101 0110010001001110 100100001001110 00100010011011 1011101010010 0101100010111 11000101011110...
output:
55
result:
ok answer is '55'
Test #49:
score: 0
Accepted
time: 2ms
memory: 7860kb
input:
100 0011010101001011 111010010100000 11001010101 01110011100000 00111110000011 0111000101001 011011100001 1011101010110011 0011010000000 1111001100000 10101110000 000001101010101 0100010000111 011000010101 00011100101101 0010011011110001 01111110001111 01100111010 011101001011001 11011001010000 0110...
output:
59
result:
ok answer is '59'
Test #50:
score: 0
Accepted
time: 0ms
memory: 7856kb
input:
3 1101 1 10
output:
4
result:
ok answer is '4'
Test #51:
score: 0
Accepted
time: 1ms
memory: 7860kb
input:
100 1000000010110000 1010110000101101 11001011110100 100101100101 110100110110100 0110000100111110 101110101110 1010101000110 1011000101100 0001001110001100 11000111010 1110011100010 00010110110011 10100010100 00010011011011 10101011111101 000001010101101 0111111001010011 01110111101 00101110100 100...
output:
61
result:
ok answer is '61'
Test #52:
score: 0
Accepted
time: 1ms
memory: 8072kb
input:
100 110000101000110 1000111101010101 100001101101 10100101101 01101010101101 11111110101 0111010101111001 011001001000 0111011000010 1101100101010 01111110101100 10111000010 0000111100001 001011010100 1010111101000 11111110110010 0101101001010100 10111010001011 01110100011100 0001110011111010 011010...
output:
62
result:
ok answer is '62'
Test #53:
score: 0
Accepted
time: 2ms
memory: 7924kb
input:
5 01000100111 01 000100111 010101 01010101
output:
6
result:
ok answer is '6'
Test #54:
score: 0
Accepted
time: 0ms
memory: 7876kb
input:
67 1 1111111111111110 0111111111111100 0011111111111000 0001111111111000 0001111111111010 0101111111110000 0000111111110010 0010111111110100 0100111111110110 0110111111100000 0000011111100010 0001011111100100 0010011111100110 0011011111101000 0100011111101010 0101011111101100 0110011111101110 011101...
output:
654
result:
ok answer is '654'
Test #55:
score: 0
Accepted
time: 2ms
memory: 7928kb
input:
100 00000101101 10000010111 010000101111 111011101101100 111110100101 100000000010100 011111111110 010011110011010 01110001111 011011000000011 100011110110100 001011111101101 100010110000 11110000110101 0011001011110 110110111101000 0001000110001 000100101101 00101010110 1101111001001100 01110111100...
output:
67
result:
ok answer is '67'
Test #56:
score: 0
Accepted
time: 2ms
memory: 7864kb
input:
100 1000111110000111 10100111010 01000010011110 000100110100000 0111100111001101 1011110000111011 11101001010010 01001110010010 110010110001 00011111001 11110100100110 1110111110010110 1110000101011110 1001010100000 1111100100110 00000100001011 000000011110 10000000010 10001001000000 010010010111010...
output:
68
result:
ok answer is '68'
Test #57:
score: 0
Accepted
time: 2ms
memory: 7864kb
input:
10 1100 100 000 01111 111 1110 10011 101 110 0101
output:
7
result:
ok answer is '7'
Test #58:
score: 0
Accepted
time: 1ms
memory: 7876kb
input:
100 0010100010100101 00000111111010 1000001110111 10101000110 010100100011 0110001011001 11111110001 000000110110110 1010001011010 10011000011 0111101100110101 1111100100000100 011011010011 00001011100 1001000101001001 111011111010111 01001010001 110001000111 1100001110001 001011111001 11000101000 1...
output:
80
result:
ok answer is '80'
Test #59:
score: 0
Accepted
time: 0ms
memory: 8072kb
input:
100 0000010010101100 110011111110 0110001100111 000100001001 1001011100111101 00101100001100 11011101001011 11000110011 00111001011 0101011100111 1100001101100101 01100100101 0110000110100000 01011010101 1000110010010 11011111011011 001000111110 111000101000 01101110110011 0010010011001111 110100001...
output:
83
result:
ok answer is '83'
Test #60:
score: 0
Accepted
time: 2ms
memory: 7924kb
input:
10 11001 11000 1111 1010 001 10011 1011 01011 100 01110
output:
8
result:
ok answer is '8'
Test #61:
score: 0
Accepted
time: 2ms
memory: 7860kb
input:
4 00010101 000 10 1
output:
8
result:
ok answer is '8'
Test #62:
score: 0
Accepted
time: 2ms
memory: 7924kb
input:
10 001 110 010110 00111 101100 001011 1011 111 10101 0000
output:
9
result:
ok answer is '9'
Test #63:
score: 0
Accepted
time: 0ms
memory: 7948kb
input:
10 011 111111 010 1101 00101 11010 110000 00011 1001 001
output:
9
result:
ok answer is '9'