Submission #1213649

#TimeUsernameProblemLanguageResultExecution timeMemory
1213649i_love_springThree Friends (BOI14_friends)C++20
0 / 100
446 ms129440 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ar array void solve() { int n; cin >> n; string s; cin >> s; if (n % 2 == 0) { cout << "NOT POSSIBLE"; return; } set<int> ans; set<ar<int,2>> bugs; for (int i = 0; i < n / 2;i++) { if (s[i] != s[i + n / 2 + 1]) bugs.insert({i, i + n / 2 + 1}); } auto bl = bugs; auto br = bugs; for (int i = 1; i <= n / 2;i++) { int l = n / 2 - i; int r = n / 2 + i; //cerr << l << " " << l + n / 2 + 1 << " " << n / 2 - i + 1 << "\n"; if (s[l] != s[l + n / 2 + 1]) { bl.erase({l, l + n / 2 + 1}); } if (s[n / 2 - i + 1] != s[l + n / 2 + 1]) { bl.insert({n / 2 - i + 1, l + n / 2 + 1}); } // cerr << r << " " << r - n / 2 - 1 << " " << n / 2 + i - 1 << "\n"; if (s[r] != s[r - n / 2 - 1]) { br.erase({ r - n / 2 - 1,r}); } if (s[n / 2 + i - 1] != s[r - n / 2 - 1]) { br.insert({r - n / 2 - 1,n / 2 + i - 1 }); } if (bl.empty()) ans.insert(l); if (br.empty()) ans.insert(r); } if (ans.size() > 1) cout << "NOT UNIQUE"; else if (ans.empty()) cout << "NOT POSSIBLE"; else { int cnt = 0,ok = 0; for (int i = 0; cnt < n / 2;i++) { if (ok == 0 && ans.count(i)) { ok = 1; continue; } cout << s[i]; cnt++; } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; //cin >> t; while (t--) { solve(); cout << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...