제출 #794343

#제출 시각아이디문제언어결과실행 시간메모리
794343bane세 명의 친구들 (BOI14_friends)C++17
0 / 100
875 ms85332 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") /* #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; */ #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep1(i, n) for (int i = 1; i < (n); ++i) #define rep1n(i, n) for (int i = 1; i <= (n); ++i) #define repr(i, n) for (int i = (n) - 1; i >= 0; --i) #define fr first #define sc second #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define endl '\n' using ll = long long; using ull = unsigned long long; using ld = long double; using str = string; using pi = pair<int, int>; using pl = pair<ll, ll>; using vi = vector<int>; using vl = vector<ll>; using vpi = vector<pair<int, int>>; using vvi = vector<vi>; const int nax = (int)2000002; int n, p = 31, m = (int)1e9 + 7; ll hsh[nax]; string s; ll bpow(ll u, ll b){ ll res = 1; while(b){ if (b & 1)res = (res * u)%m; b /= 2; u*=u; u%=m; } return res; } ll inv(ll p){ return bpow(p,m-2); } void solve(){ cin >> n >> s; if (n % 2 == 0){ cout << "NOT POSSIBLE" << endl; return; } ll ps[n+1]; ps[0] = 1; for (int i = 1; i <= n; i++){ ps[i] = p; ps[i] *= ps[i - 1]; ps[i] %= m; } ll ips[n + 1]; for (int i = 0; i <= n; i++){ ips[i] = inv(ps[i]); } for (int i = 0; i < n; i++){ hsh[i] = (s[i] - 'A' + 1) * ps[i] % m; if (i)hsh[i] += hsh[i - 1]; hsh[i]%=m; } //cout << hsh[0] << endl; //cout << ps[3] << endl; int L1[n], R1[n], L2[n], R2[n]; unordered_set<ll>se; string res = ""; for(int i = 0; i < n; i++){ L1[i] = 0; if (i == 0)L1[i]++; R1[i] = L1[i] + n / 2 - 1; if (R1[i] >= i && L1[i] < i)R1[i]++; ll hash1 = 0; if (R1[i] > i && L1[i] < i){ hash1 = (i < 1 ? 0 : hsh[i - 1]); hash1 += ((hsh[R1[i]] - hsh[i]) * ips[i + 1]%m) * ps[i] % m; }else{ hash1 = hsh[R1[i]]; if (L1[i]){ hash1 -= hsh[L1[i] - 1]; hash1 %= m; hash1 *= ips[L1[i]]; } hash1 %= m; } L2[i] = R1[i] + 1; if (L2[i] == i)++L2[i]; R2[i] = L2[i] + n / 2 - 1; ll hash2 = 0; if (R2[i] >= i && L2[i] < i)++R2[i]; //cout << L1[i] << " " << R1[i] << " " << L2[i] << " " << R2[i] << endl; if (L2[i] > i){ hash2 = hsh[R2[i]] - hsh[L2[i] - 1]; hash2 *= ips[L2[i]]; hash2 %= m; }else{ hash2 = hsh[i - 1] - hsh[L2[i] - 1]; hash2 *= ips[L2[i]]; hash2 %= m; ll hash3 = hsh[R2[i]] - hsh[i]; hash3 *= ips[i+1]; hash3 %= m; hash3 *= ps[i - L2[i]]; hash3 %= m; if (i - 1 != R2[i]) hash2 += hash3; } if (hash1 == hash2){ if (se.empty()){ for (int j = 0; j < n; j++){ if (i == j)continue; if (res.size() < n / 2)res += s[j]; else break; } } se.insert(hash1); if (se.size() > 1){ cout << "NOT UNIQUE" << endl; return; } } } if (se.empty())cout << "NOT POSSIBLE" << endl; else cout << res << endl; } int main(){ ios::sync_with_stdio(0); cin.tie(0); int tt = 1; //cin >> tt; while(tt--){ solve(); } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

friends.cpp: In function 'void solve()':
friends.cpp:140:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |      if (res.size() <  n / 2)res += s[j];
      |          ~~~~~~~~~~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...