QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#852143#7686. The Phantom MenaceOoj_baiWA 8ms128492kbC++144.1kb2025-01-11 10:18:492025-01-11 10:18:55

Judging History

This is the latest submission verdict.

  • [2025-01-11 10:18:55]
  • Judged
  • Verdict: WA
  • Time: 8ms
  • Memory: 128492kb
  • [2025-01-11 10:18:49]
  • Submitted

answer

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#ifndef _WINDOWS_
    #define gc() getchar_unlocked()
    #define pc(ch) putchar_unlocked(ch)
#endif
#define maxn 2000005
#define mod 998244353
#define BASE 131
using namespace std;
typedef long long ll;
namespace FASTIO{
    int read(){
        int x=0,w=0;
        char ch=' ';
        while(!isdigit(ch)){
            if(ch=='-')
                w=1;
            ch=gc();
        }
        while(isdigit(ch)){
            x=x*10+ch-'0';
            ch=gc();
        }
        return (w?-x:x);
    }
    int __fastwrite_stack[45],__fastwrite_top;
    inline void write(int x){
        __fastwrite_top=0;
        do{
            __fastwrite_stack[__fastwrite_top++]=x%10;
            x/=10;
        }while(x);
        while(__fastwrite_top--)pc(__fastwrite_stack[__fastwrite_top]+'0');
    }
    char readc(){
        char ch=' ';
        while(ch<'a'||ch>='z')ch=gc();
        return ch;
    }    
}
using namespace FASTIO;

struct edge{
    int next;
    pair<int,int>to;
}e[maxn<<2];
int h[maxn<<2],cnt;
void add(int x,const pair<int,int> &y){
    e[++cnt]={h[x],y};
    h[x]=cnt;
}
int t,n,m;
int base[maxn];
char f[maxn];
int ls[maxn],lss[maxn];
int *D[maxn],*_D[maxn];
pair<int,bool> lsh[maxn<<2];
int vis[maxn<<2];
void dfs(int x,int *ans,int &n){
    vis[x]=1;
    for(int i=h[x];i;i=h[x]){
        pair<int,int> itt=e[i].to;
        h[x]=e[i].next;
        dfs(itt.first,ans,n);
        ans[++n]=itt.second;
    }
}
int rd[maxn<<2],cd[maxn<<2];
int x[maxn],y[maxn];
int ans[maxn<<2];
signed main(){
    base[0]=1;
    for(int i=1;i<=1e6;i++)base[i]=base[i-1]*BASE%mod;
    cin>>t;
    while(t--){
        n=read();m=read();
        for(int i=0;i<2*n;i++){
            D[i]=ls+i*m;
            _D[i]=lss+((i+1)*m-1);
            for(int j=0;j<m;j++){
                f[j]=readc();
                D[i][j]=(j?D[i][j-1]+(ll)base[j]*f[j]:f[j])%mod;
            }
            for(int j=m-1;j>=0;j--)
                _D[i][j]=(j==m-1?f[j]:(ll)BASE*_D[i][j+1]+f[j])%mod;
        }
        int ok=0;
        for(int i=0;i<m;i++){
            int cnt=-1;
            lsh[++cnt]={0,0};
            for(int j=0;j<n;j++){
                if(i)lsh[++cnt]={D[j][i-1],0};
                lsh[++cnt]={_D[j][i],1};
            }
            for(int j=n;j<2*n;j++){
                lsh[++cnt]={D[j][m-i-1],1};
                if(i)lsh[++cnt]={_D[j][m-i],0};
            }
            sort(lsh,lsh+cnt+1);
            cnt=unique(lsh,lsh+cnt+1)-lsh;
            ::cnt=0;
            for(int j=0;j<=cnt;j++)
                vis[j]=h[j]=rd[j]=cd[j]=0;
            for(int j=0;j<n;j++){
                int x=lower_bound(lsh,lsh+cnt+1,pair<int,bool>{(i?D[j][i-1]:0),0})-lsh;
                int y=lower_bound(lsh,lsh+cnt+1,pair<int,bool>{_D[j][i],1})-lsh;
                add(x,{y,j});
                cd[x]++;rd[y]++;
            }
            for(int j=n;j<2*n;j++){
                int x=lower_bound(lsh,lsh+cnt+1,pair<int,bool>{D[j][m-i-1],1})-lsh;
                int y=lower_bound(lsh,lsh+cnt+1,pair<int,bool>{(i?_D[j][m-i]:0),0})-lsh;
                add(x,{y,j});
                cd[x]++;rd[y]++;
            }
            int bj=1;
            for(int j=0;j<=cnt;j++)
                if(rd[j]!=cd[j]){
                    bj=0;break;
                }
            if(bj){
                int ccnt=0;
                for(int j=0;j<=cnt;j++)
                    if(!vis[j])
                        dfs(j,ans,ccnt); 
                int cnt1=0,cnt2=0;
                for(int j=1;j<=ccnt;j++){
                    int num=ans[j];
                    if(num<n){
                        x[++cnt1]=num+1;
                    }else{
                        y[++cnt2]=num-n+1;
                    }
                }
                for(int j=1;j<=n;j++)write(x[j]),pc(' ');pc('\n');
                for(int j=1;j<=n;j++)write(y[j]),pc(' ');pc('\n');
                ok=1;
                break;
            }
        }
        if(!ok){
            pc('-');pc('1');pc('\n');
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 8ms
memory: 128492kb

input:

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

output:

2 3 1 
3 2 1 
-1

result:

wrong answer not cyclic isomorphism (test case 1)