QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #37431 | #1193. Ambiguous Encoding | jiaangk | WA | 41ms | 69236kb | C++ | 3.1kb | 2022-07-01 13:57:52 | 2022-07-01 13:57:53 |
Judging History
answer
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define pb push_back
#define st first
#define nd second
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
template <class T> void read(T &a) {
a=0;char x=getchar();bool f=0;
for(;x<'0'||x>'9';x=getchar())f|=x=='-';
for(;x>='0'&&x<='9';x=getchar())a=(a<<3)+(a<<1)+x-'0';
if(f)a=-a;
}
template <class T, class... Args> void read(T &a, Args&...args) {
read(a);
read(args...);
}
using namespace std;
const int N = 1e5 + 5;
struct node {
int ch[2], d;
bool ok;
}pnt[N];
char s[25];
int ans = INF;
queue<set<int> > q[100005];
int n, cnt;
set<set<int> > ST;
void ins(int pos, int cur = 0) {
if (s[pos] == 0) {
if (pnt[cur].ok) {
ans = min(ans, pos);
}
pnt[cur].ok = 1;
pnt[cur].d = 1;
return;
}
int now = s[pos] - '0';
if (!pnt[cur].ch[now]) {
pnt[cur].ch[now] = ++cnt;
}
ins(pos + 1, pnt[cur].ch[now]);
pnt[cur].d = pnt[cur].ok;
if (pnt[cur].ch[0]) pnt[cur].d += pnt[pnt[cur].ch[0]].d;
if (pnt[cur].ch[1]) pnt[cur].d += pnt[pnt[cur].ch[1]].d;
}
int main() {
read(n);
for (int i = 1; i <= n; ++i) {
scanf("%s", s);
ins(0);
}
set<int> x;
x.insert(0);
q[1].push(x);
ST.insert(x);
for (int i = 1; !q[i].empty();++i) {
while (!q[i].empty()) {
x = q[i].front();
q[i].pop();
set<int> zero, one;
int totz, toto;
totz = toto = 0;
for (auto id: x) {
if (pnt[id].ch[0]) {
zero.insert(pnt[id].ch[0]);
totz += pnt[pnt[id].ch[0]].d;
if (pnt[pnt[id].ch[0]].ok) {
if (zero.count(0)) {
ans = min(ans, i);
goto mark;
}
zero.insert(0);
totz += pnt[0].d;
}
}
if (pnt[id].ch[1]) {
one.insert(pnt[id].ch[1]);
toto += pnt[pnt[id].ch[1]].d;
if (pnt[pnt[id].ch[1]].ok) {
if (one.count(0)) {
ans = min(ans, i);
goto mark;
}
one.insert(0);
toto += pnt[0].d;
}
}
}
if (totz > 1) {
if (!ST.count(zero)) {
ST.insert(zero);
q[i + 1].push(zero);
}
}
if (toto > 1) {
if (!ST.count(one)) {
ST.insert(one);
q[i + 1].push(one);
}
}
}
}
mark:
if (ans == INF) {
puts("0");
return 0;
}
printf("%d\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 27ms
memory: 68428kb
input:
3 0 01 10
output:
3
result:
ok answer is '3'
Test #2:
score: 0
Accepted
time: 41ms
memory: 67984kb
input:
3 00 01 1
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 21ms
memory: 67612kb
input:
3 00 10 1
output:
0
result:
ok answer is '0'
Test #4:
score: 0
Accepted
time: 23ms
memory: 69084kb
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: 22ms
memory: 68584kb
input:
3 1101 1 10
output:
4
result:
ok answer is '4'
Test #6:
score: 0
Accepted
time: 21ms
memory: 69228kb
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: 33ms
memory: 69236kb
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: 37ms
memory: 67856kb
input:
10 1001 10111 11011 00010 001 001100 110 01110 111101 11100
output:
10
result:
ok answer is '10'
Test #9:
score: -100
Wrong Answer
time: 19ms
memory: 68664kb
input:
10 0001 0101 1001 101 0010 010 00000 1000 00001 111101
output:
0
result:
wrong answer expected '10', found '0'