1 条题解
-
0
#include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; // 定义新的无符号长整型 #define rep(i, l, r) for(int i = l; i <= r; ++i) #define per(i, r, l) for(int i = r; i >= l; --i) const int N = 2e6 + 10; int n, mid, ans_id, tot; string s; const int base = 133331, p = 1e9 + 7; ull G[N], f[N]; unordered_map<ull, bool> vis; void init() { G[0] = 1; rep(i, 1, n) { G[i] = G[i - 1] * base; f[i] = f[i - 1] * base + s[i]; } } ull calc(int l, int r) { return f[r] - f[l - 1] * G[r - l + 1]; } ull del_calc(int l, int x, int r) { return calc(l, x - 1) * G[r - x] + calc(x + 1, r); } bool check(int x) { ull l = 0, r = 0; if (x == mid) { l = calc(1, x - 1); r = calc(x + 1, n); } if (x < mid) { l = del_calc(1, x, mid); r = calc(mid + 1, n); } if (x > mid) { l = calc(1, mid - 1); r = del_calc(mid, x, n); } if (l == r && !vis[l]) { vis[l] = true; return true; } return false; } int main() { cin >> n >> s; s = "0" + s; if (!(n & 1)) { puts("NOT POSSIBLE"); exit(0); } mid = (n + 1) >> 1; init(); rep(i, 1, n) { if (check(i)) { ans_id = i; tot++; } } if (tot > 1) { puts("NOT UNIQUE"); exit(0); } if (!tot) { puts("NOT POSSIBLE"); exit(0); } if (ans_id == mid) rep(i, 1, mid - 1) cout << s[i]; else if (ans_id < mid) rep(i, mid + 1, n) cout << s[i]; else rep(i, 1, mid - 1) cout << s[i]; return 0; }
- 1
信息
- ID
- 915
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- (无)
- 递交数
- 0
- 已通过
- 0
- 上传者