QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#561088	#7686. The Phantom Menace	lyxeason	WA	306ms	158340kb	C++14	3.3kb	2024-09-12 20:02:58	2024-09-12 20:02:58

Judging History

你现在查看的是最新测评结果

[2024-10-08 14:11:03]
hack成功，自动添加数据
(/hack/941)

[2024-10-08 10:05:28]
hack成功，自动添加数据
(/hack/940)

[2024-10-07 19:51:15]
hack成功，自动添加数据
(/hack/938)

[2024-10-07 19:28:01]
hack成功，自动添加数据
(/hack/937)

[2024-10-07 17:16:32]
hack成功，自动添加数据
(/hack/936)

[2024-10-07 16:53:09]
hack成功，自动添加数据
(/hack/935)

[2024-10-07 16:22:17]
hack成功，自动添加数据
(/hack/934)

[2024-09-12 20:02:58]
评测

测评结果：WA
用时：306ms
内存：158340kb

查看

[2024-09-12 20:02:58]
提交

answer



#include <map>
#include <cstdio>
#include <vector>
#define ull unsigned long long

using namespace std;

const ull D = 131;
int T;
int N;
int M;
vector<int> idA1[1000009];
vector<int> idA2[1000009];
vector<int> idB1[1000009];
vector<int> idB2[1000009];
char s[1000009];
struct Node {
    int v;
    int id;
};
ull PD[1000009];
vector<Node> E[2000009];
int deg2[2000009];
int idx;
map<ull, int> S;
int ba[2000009];
bool va[2000009];
int n;
int resa[1000009];
int resb[1000009];
int a;
int b;

void Dfs (int x) {
    Node v;
    while (!E[x].empty()) {
        v = E[x].back(), E[x].pop_back();
        if (v.id <= N) resa[++a] = v.id;
        else resb[++b] = v.id - N;
        Dfs(v.v);
    }
}

int main () {
    ull s1;
    ull s2;
    bool f;
    PD[0] = 1;
    for (int i = 1; i <= 1000000; i++) PD[i] = PD[i - 1] * D;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &M);
        S.clear(), idx = 0;
        for (int i = 1; i <= N; i++) {
            scanf("%s", s + 1);
            idA1[i].clear(), idA2[i].clear();
            s1 = s2 = 0;
            idA1[i].push_back(0), idA2[i].push_back(0);
            for (int j = 1; j <= M; j++) {
                s1 = s1 * D + (ull)(s[j] - 'a' + 1), s2 = s2 + PD[j - 1] * (ull)(s[M - j + 1] - 'a' + 1);
                a = S[s1];
                if (!a) a = S[s1] = ++idx;
                idA1[i].push_back(a);
                a = S[s2];
                if (!a) a = S[s2] = ++idx;
                idA2[i].push_back(a);
            }
        }
        for (int i = 1; i <= N; i++) {
            scanf("%s", s + 1);
            idB1[i].clear(), idB2[i].clear();
            s1 = s2 = 0;
            idB1[i].push_back(0), idB2[i].push_back(0);
            for (int j = 1; j <= M; j++) {
                s1 = s1 * D + (ull)(s[j] - 'a' + 1), s2 = s2 + PD[j - 1] * (ull)(s[M - j + 1] - 'a' + 1);
                a = S[s1];
                if (!a) a = S[s1] = ++idx;
                idB1[i].push_back(a);
                a = S[s2];
                if (!a) a = S[s2] = ++idx;
                idB2[i].push_back(a);
            }
        }
        f = false;
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= n; j++) E[ba[j]].clear(), va[ba[j]] = deg2[ba[j]] = 0;
            n = 0;
            for (int j = 1; j <= N; j++) {
                a = idA1[j][i], b = idA2[j][M - i];
                if (!va[a]) va[a] = true, ba[++n] = a;
                if (!va[b]) va[b] = true, ba[++n] = b;
                E[a].push_back({b, j});
                deg2[b]++;
                a = idB1[j][M - i], b = idB2[j][i];
                if (!va[a]) va[a] = true, ba[++n] = a;
                if (!va[b]) va[b] = true, ba[++n] = b;
                E[a].push_back({b, j + N});
                deg2[b]++;
            }
            f = true;
            for (int j = 1; j <= n; j++)
                if (deg2[ba[j]] != E[ba[j]].size()) {
                    f = false;
                    break;
                }
            if (!f) continue;
            a = b = 0;
            Dfs(ba[1]);
            if (a < N || b < N) {
                f = false;
                continue;
            }
            for (int j = 1; j <= N; j++) printf("%d ", resa[j]);
            puts("");
            for (int j = 1; j <= N; j++) printf("%d ", resb[j]);
            puts("");
            break;
        }
        if (!f) puts("-1");
    }
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 19ms

memory: 156384kb

input:

2
3 3
abc
ghi
def
bcd
efg
hia
1 3
abc
def

output:

1 3 2 
1 2 3 
-1

result:

ok 2 cases (2 test cases)

Test #2:

score: 0

Accepted

time: 306ms

memory: 158340kb

input:

1000000
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
...

output:

result:

ok 1000000 cases (1000000 test cases)

Test #3:

score: 0

Accepted

time: 201ms

memory: 154444kb

input:

500000
1 2
dd
ba
1 2
cd
ba
1 2
bd
ba
1 2
ad
ba
1 2
dc
ba
1 2
cc
ba
1 2
bc
ba
1 2
ac
ba
1 2
db
ba
1 2
cb
ba
1 2
bb
ba
1 2
ab
ba
1 2
da
ba
1 2
ca
ba
1 2
ba
ba
1 2
aa
ba
1 2
dd
aa
1 2
cd
aa
1 2
bd
aa
1 2
ad
aa
1 2
dc
aa
1 2
cc
aa
1 2
bc
aa
1 2
ac
aa
1 2
db
aa
1 2
cb
aa
1 2
bb
aa
1 2
ab
aa
1 2
da
aa
1 2...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 
1 
-1
-1
1 
1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 
1 
1 
1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 
1 
-1
-1
1 
1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 
1 
-1
-1
-1
-1
-1
1 
1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 
1 
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 500000 cases (500000 test cases)

Test #4:

score: 0

Accepted

time: 224ms

memory: 153252kb

input:

500000
2 1
d
d
b
a
2 1
c
d
b
a
2 1
b
d
b
a
2 1
a
d
b
a
2 1
d
c
b
a
2 1
c
c
b
a
2 1
b
c
b
a
2 1
a
c
b
a
2 1
d
b
b
a
2 1
c
b
b
a
2 1
b
b
b
a
2 1
a
b
b
a
2 1
d
a
b
a
2 1
c
a
b
a
2 1
b
a
b
a
2 1
a
a
b
a
2 1
d
d
a
a
2 1
c
d
a
a
2 1
b
d
a
a
2 1
a
d
a
a
2 1
d
c
a
a
2 1
c
c
a
a
2 1
b
c
a
a
2 1
a
c
a
a
2 1
d...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 2 
2 1 
-1
-1
1 2 
2 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2 1 
2 1 
2 1 
2 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 2 
2 1 
-1
-1
1 2 
2 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 2 
2 1 
-1
-1
-1
-1
-1
1 2 
2 1 
-1
-1
-1
-1
-1
-1
-1
-1
-...

result:

ok 500000 cases (500000 test cases)

Test #5:

score: 0

Accepted

time: 211ms

memory: 154408kb

input:

333333
1 3
cbb
bfa
1 3
bbb
bfa
1 3
abb
bfa
1 3
fab
bfa
1 3
eab
bfa
1 3
dab
bfa
1 3
cab
bfa
1 3
bab
bfa
1 3
aab
bfa
1 3
ffa
bfa
1 3
efa
bfa
1 3
dfa
bfa
1 3
cfa
bfa
1 3
bfa
bfa
1 3
afa
bfa
1 3
fea
bfa
1 3
eea
bfa
1 3
dea
bfa
1 3
cea
bfa
1 3
bea
bfa
1 3
aea
bfa
1 3
fda
bfa
1 3
eda
bfa
1 3
dda
bfa
1 3
c...

output:

-1
-1
-1
1 
1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 
1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 
1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 333333 cases (333333 test cases)

Test #6:

score: -100

Wrong Answer

time: 198ms

memory: 152848kb

input:

333333
3 1
c
b
b
b
f
a
3 1
b
b
b
b
f
a
3 1
a
b
b
b
f
a
3 1
f
a
b
b
f
a
3 1
e
a
b
b
f
a
3 1
d
a
b
b
f
a
3 1
c
a
b
b
f
a
3 1
b
a
b
b
f
a
3 1
a
a
b
b
f
a
3 1
f
f
a
b
f
a
3 1
e
f
a
b
f
a
3 1
d
f
a
b
f
a
3 1
c
f
a
b
f
a
3 1
b
f
a
b
f
a
3 1
a
f
a
b
f
a
3 1
f
e
a
b
f
a
3 1
e
e
a
b
f
a
3 1
d
e
a
b
f
a
3 1
c...

output:

-1
-1
-1
1 2 3 
3 2 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 3 2 
3 2 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 3 2 
3 2 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2 1 3 
3 2 1 
-1
-1
-1
-1
-...

result:

wrong answer not cyclic isomorphism (test case 4)