2 条题解

  • 0
    @ 2023-11-18 21:01:37
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #include <queue>
    #include <map>
    #define ll  long long
    #define out(a) printf("%d ",a)
    #define writeln printf("")
    const int N=2e6+50;
    const int MOD=1e9+7;
    const int base=233;
    using namespace std;
    char s[N];
    int n,len,id;
    int num,ans,cnt=0;
    bool f,flag;
    ll Hash[N],Pow[N];
    int read()
    {
        int s=0,t=1; char c;
        while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
        while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
        return s*t;
    }
    ll readl()
    {
        ll s=0,t=1; char c;
        while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
        while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
        return s*t;
    }
    ll get(int l,int r)
    {
        if (l<=r) return (Hash[r]-(ll)Hash[l-1]*Pow[r-l+1]%MOD+MOD)%MOD;
        else return 0;
    }
    ll find(int x)
    {
        ll y1=0,y2=0;
        if (x<=(n>>1)) y1=(get(0,x-1)*Pow[(n>>1)-x]%MOD+get(x+1,n>>1))%MOD,y2=get((n>>1)+1,n-1);
        else y1=get(0,(n>>1)-1),y2=(get((n>>1),x-1)*Pow[n-x-1]%MOD+get(x+1,n-1))%MOD;
        //out(y1); out(y2); writeln;
        if (y1==y2) return y1;
        else return 0;
    }
    int main()
    {
        n=read();
        if (!(n&1)) {
          puts("NOT POSSIBLE");
          return 0;
        }
        else {
          scanf("%s",s);
          len=strlen(s); f=flag=false;
          Pow[0]=1;
          for (int i=1;i<=len;i++)
            Pow[i]=Pow[i-1]*base%MOD;
          for (int i=0;i<len;i++)
            Hash[i]=(Hash[i-1]*base+s[i])%MOD;
          for (int i=0;i<len;i++){
            num=find(i);
            if (num) {
                //out(233); writeln;
              if (!f) ans=num,id=i;
              else if (ans!=num) {
                  flag=true; break;
              }
              f=true;
            }
          }
          if (f) {
            if (flag) puts("NOT UNIQUE");
            else {
              for (int i=0;i<len;i++){
                if (i!=id) putchar(s[i]),cnt++;
                if (cnt>=(n>>1)) break;
              }
            }
          }
          else puts("NOT POSSIBLE");
        }
          return 0;
    }
    

    信息

    ID
    380
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    178
    已通过
    7
    上传者