QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#802626#8668. 回文路径flowing_boat0 22ms15068kbC++146.8kb2024-12-07 14:13:082024-12-07 14:13:09

Judging History

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

  • [2024-12-07 14:13:09]
  • 评测
  • 测评结果:0
  • 用时:22ms
  • 内存:15068kb
  • [2024-12-07 14:13:08]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO{
    #define IOSIZE (1<<20)
    char ibuf[IOSIZE],obuf[IOSIZE];char*p1=ibuf,*p2=ibuf,*p3=obuf;
    #ifdef ONLINE_JUDGE
    #define putchar(x)((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
    #endif
    #define isdigit(ch)(ch>47&&ch<58)
    #define isspace(ch)(ch<33)
    template	<typename T>inline T    read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*1+ch-48,ch=getchar();return s*w;}template<typename T>inline bool read(T&s){s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*=w,true;}template<typename T>inline void print(T x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+48);}inline bool read(char&s){while(s=getchar(),isspace(s));return true;}inline bool read(char*s){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return true;}inline void print(char x){putchar(x);}inline void print(char*x){while(*x)putchar(*x++);}inline void print(const char*x){for(int i=0;x[i];i++)putchar(x[i]);}inline bool read(std::string&s){s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))s+=ch,ch=getchar();return true;}inline void print(std::string x){for(int i=0,n=x.size();i<n;i++)putchar(x[i]);}inline bool read(bool&b){char ch;while(ch=getchar(),isspace(ch));b=ch^48;return true;}inline void print(bool b){putchar(b+48);}template<typename T,typename...T1>inline int read(T&a,T1&...other){return read(a)+read(other...);}template<typename T,typename...T1>inline void print(T a,T1...other){print(a),print(other...);}struct Fast_IO{~Fast_IO(){fwrite(obuf,p3-obuf,1,stdout);}}jyt;template<typename T>Fast_IO&operator>>(Fast_IO&jyt,T&b){return read(b),jyt;}template<typename T>Fast_IO&operator<<(Fast_IO&jyt,T b){return print(b),jyt;}
    struct IO{static const int S=1<<21;char buf[S],*p1,*p2;int st[105],Top;~IO(){clear();}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}IO&operator>>(char&x){while(x=gc(),x==' '||x=='\n');return*this;}template<typename T>IO&operator>>(T&x){x=0;bool f=0;char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-')f^=1;ch=gc();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=gc();f?x=-x:0;return*this;}IO&operator<<(const char c){pc(c);return*this;}template<typename T>IO&operator<<(T x){if(x<0)pc('-'),x=-x;do{st[++st[0]]=x%10,x/=10;}while(x);while(st[0]){pc('0'+st[st[0]--]);}return*this;}}ld;
} using namespace fast_IO;
#define ll long long
#define ull unsigned long long
#define REP(i, l, r) for (int i = l; i <= r; ++i)
#define PER(i, l, r) for (int i = l; i >= r; --i)
#define rep(i, l, r) for (int i = l; i < r ; ++i)
#define per(i, l, r) for (int i = l; i > r ; --i)
namespace RPD {
    #define pf(x) ((x) * (x))
    #define ppf(x) ((x) * (x) * (x))
    #define modf(x, mod) (((x) % mod + mod) % mod)
    #define min3(x, y, z) (min(x, min(y, z)))
    #define min4(x, y, z, w) (min(min(x, y), min(z, w)))
    #define max3(x, y, z) (max(x, max(y, z)))
    #define max4(x, y, z, w) (max(max(x, y), max(z, w)))
    #define gmin(x, y) (x = min(x, y))
    #define gmax(x, y) (x = max(x, y))
    #define lowbit(x) (x & -x) 
    #define bitcount(x) __builtin_popcount(x)
    #define albit(x) ((1 << (x)) - 1)
    #define mkbit(x) (1 << (x))
    #define gtbit(x, id) (((x) >> (id)) & 1)
}
// #define ld cin
// #define jyt cout
// #define int long long
const int N = 2e5 + 7;
const int inf = 1e9 + 7;
const ll linf = 1e18 + 7;
const ll Base = 2077;
const ll P = 998244353;
namespace JoKing {
    int n, Ans = 0; string S[2];
    ll base[N];
    struct HASH {
        ll H[2][N];
        inline ll gh(int op, int l, int r) {return (H[op][r] - H[op][l - 1] + P) * base[n - r] % P;}
        inline ll fgh(int op, int l, int r) {return gh(op, n - r + 1, n - l + 1);}
    } A, B;

    inline void solve() {
        REP(i, 1, n) { // Mid = i(0)
            int L = 1, R = min(i, n - i + 1), Res1 = 0, Res2 = 0;
            while (L <= R) {
                int mid = (L + R) >> 1;
                if (A.gh(0, i - mid + 1, i) == B.fgh(0, i, i + mid - 1)) L = mid + 1, Res1 = mid;
                else R = mid - 1;
            } Ans = max(Ans, Res1 * 2 - 1);
            L = 1, R = min(i - Res1, n - (i + Res1 - 1) + 1), Res2 = 0;
            while (L <= R) {
                int mid = (L + R) >> 1;
                if (A.gh(0, i - Res1 - mid + 1, i - Res1) == B.fgh(1, i + Res1 - 1, i + Res1 - 1 + mid - 1)) L = mid + 1, Res2 = mid;
                else R = mid - 1;
            } Ans = max(Ans, (Res1 + Res2) * 2 - 1);
        }
        REP(i, 1, n - 1) { // Mid = i(0) ~ i + 1(0)
            int L = 1, R = min(i, n - i), Res1 = 0, Res2 = 0;
            while (L <= R) {
                int mid = (L + R) >> 1;
                if (A.gh(0, i - mid + 1, i) == B.fgh(0, i + 1, i + mid)) L = mid + 1, Res1 = mid;
                else R = mid - 1;
            } Ans = max(Ans, Res1 * 2);
            if (!Res1) break;
            L = 1, R = min(i - Res1, n - (i + Res1) + 1), Res2 = 0;
            while (L <= R) {
                int mid = (L + R) >> 1;
                if (A.gh(0, i - Res1 - mid + 1, i - Res1) == B.fgh(1, i + Res1, i + Res1 + mid - 1)) L = mid + 1, Res2 = mid;
                else R = mid - 1;
            } Ans = max(Ans, (Res1 + Res2) * 2);
        }
    }
    signed main() {
        jyt >> n >> S[0] >> S[1], S[0] = " " + S[0], S[1] = " " + S[1], base[0] = 1;
        REP(i, 1, n) {
            base[i] = base[i - 1] * Base % P;
            A.H[0][i] = A.H[0][i - 1] + base[i - 1] * S[0][i];
            A.H[1][i] = A.H[1][i - 1] + base[i - 1] * S[1][i];
            B.H[0][i] = B.H[0][i - 1] + base[i - 1] * S[0][n - i + 1];
            B.H[1][i] = B.H[1][i - 1] + base[i - 1] * S[1][n - i + 1];
        }
        REP(i, 1, n) {
            if (A.gh(0, i, i) != A.gh(1, i, i)) continue;
            int L = 1, R = min(i, n - i + 1), Res = 0;
            while (L <= R) {
                int mid = (L + R) >> 1;
                if (A.gh(0, i - mid + 1, i) == B.fgh(1, i, i + mid - 1)) L = mid + 1, Res = mid;
                else R = mid - 1;
            } Ans = max(Ans, Res * 2);
        }
        solve();
        swap(A.H[0], A.H[1]), swap(B.H[0], B.H[1]), swap(A.H[0], B.H[0]), swap(A.H[1], B.H[1]);
        solve();
        jyt << Ans << '\n';
        return 0; 
    }
}
signed main() {
//	freopen("std.in", "r", stdin);
//	freopen("user.out", "w", stdout);
//	ios::sync_with_stdio(false);
//	cin.tie(0), cout.tie(0);
    JoKing::main();
    return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 14100kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

3

result:

wrong answer 1st lines differ - expected: '6', found: '3'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 22ms
memory: 15068kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

7

result:

wrong answer 1st lines differ - expected: '9', found: '7'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%