QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#561130	#7686. The Phantom Menace	lyxeason	WA	319ms	163248kb	C++14	3.4kb	2024-09-12 20:30:42	2024-09-12 20:30:44

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:30:44]
评测

测评结果：WA
用时：319ms
内存：163248kb

查看

[2024-09-12 20:30:42]
提交

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 res[2000009];
int resa[2000009];
int resb[2000009];
int a;
int b;
int n;

void Dfs (int x) {
    Node v;
    while (!E[x].empty()) {
        v = E[x].back(), E[x].pop_back();
        Dfs(v.v);
        res[++n] = v.id;
    }
}

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;
            Dfs(ba[1]);
            if (n < 2 * N) {
                f = false;
                continue;
            }
            a = b = 0;
            for (int j = n; j; j--)
                if (res[j] <= N) resa[++a] = res[j];
                else resb[++b] = res[j] - N;
            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: 160816kb

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: 319ms

memory: 163248kb

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: -100

Wrong Answer

time: 214ms

memory: 161504kb

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:

wrong answer not cyclic isomorphism (test case 17)