|

General

# Author Problem Lang Verdict Time Memory Sent Judged
107158701 Practice:
LTb
1200E - 114 GNU C++17 Accepted 93 ms 15156 KB 2021-02-12 05:58:59 2021-02-12 05:59:00

→ Source
// 2021.02.12 - 10:32
// Code by LTb
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define debug puts("QwQ");
int x=0,f=1;
char ch;
while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
return f*x;
}

char ch=getchar();
while (ch==' '||ch=='\n') ch=getchar();
return ch;
}

char ch=getchar();
string ans="";
while (ch==' '||ch=='\n') ch=getchar();
while (ch!=' '&&ch!='\n') {ans+=ch;ch=getchar();}
return ans;
}

inline void chmax(int &x,int y){x=max(x,y);}
inline void chmin(int &x,int y){x=min(x,y);}
// inline void pls(int &x,int y,int Mod){x=(x+y>=Mod)?(x+y-Mod):(x+y);}
// inline void red(int &x,int y,int Mod){x=(x-y<0)?(x-y+Mod):(x-y);}

const int MAXN = 100005;
const int MAXM = 2000005;
int n;
string s[MAXN];
int nex[MAXM];

string ans, y;

inline char pos(int x, int mx) {
if (x <= mx) return y[x - 1];
else if (x == mx + 1) return '#';
else return ans[ans.size() - mx + (x - mx - 1) - 1];
}

// x 是前面拼接好的，y 是待拼接的
int merge() {
int mx = min(int(ans.size()), int(y.size()));

// for (int i = 1; i <= mx * 2 + 1; i++)
// 	cout<<pos(i, mx);
// cout<<endl;

// string a = y + '#' + x;
for (int i = 2, j = 0; i <= mx * 2 + 1; i++) {
while (j > 0 && pos(i, mx) != pos(j + 1, mx)) j = nex[j];
if (pos(i, mx) == pos(j + 1, mx)) j++;
nex[i] = j;
}

return nex[mx * 2 + 1];
}

signed main()

{
for (int i = 1; i <= n; i++)

ans = s[1];
for (int i = 2; i <= n; i++) {
y = s[i];
int num = merge();
// cout << ans << ' ' << s[i] << ' ' << num << endl;
ans += s[i].substr(num);
}

cout << ans << endl;
return 0;
}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?