제출 #1014876

#제출 시각아이디문제언어결과실행 시간메모리
1014876phoenix세 명의 친구들 (BOI14_friends)C++17
100 / 100
164 ms83028 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2000010; const int MOD = 1e9 + 9; void norm(long long &x) { x = x % MOD + (x < 0) * MOD; } struct H { using ll = long long; using ull = unsigned long long; static const int base1 = 147; static const int base2 = 191; static ll pw1[N]; static ull pw2[N]; static void init() { H::pw1[0] = H::pw2[0] = 1; for (int i = 1; i < N; i++) { H::pw1[i] = H::pw1[i - 1] * base1 % MOD; H::pw2[i] = H::pw2[i - 1] * base2; } } ll h1; ull h2; int len; H () : h1(), h2(), len() {} H (char c) : len(1), h1(c), h2(c) {} H& operator += (const H &a) { len += a.len; h1 *= pw1[a.len]; h1 += a.h1; norm(h1); h2 *= pw2[a.len]; h2 += a.h2; return *this; } }; long long H::pw1[]; unsigned long long H::pw2[]; H operator + (H a, const H b) { return a += b; } H operator - (const H a, const H b) { H res; res.len = a.len - b.len; res.h1 = a.h1 - b.h1 * H::pw1[res.len]; res.h2 = a.h2 - b.h2 * H::pw2[res.len]; // res.h1 = res.h1 % H::MOD + (res.h1 < 0) * H::MOD; norm(res.h1); return res; } bool operator == (const H a, const H b) { return (a.len == b.len && a.h1 == b.h1 && a.h2 == b.h2); } bool operator != (const H a, const H b) {return !(a == b); } /* a0 * x^3 + a1 * x^2 + a2 * x^1 + a3 * x^0 a0 * x^1 + a1 * x^0 */ void print(H a) { cout << "{" << a.h1 << ' ' << a.h2 << ' ' << a.len << "}\n"; } int n; char s[N]; H hsh[N]; int main() { ios::sync_with_stdio(0); cin.tie(0); H::init(); cin >> n; for (int i = 1; i <= n; i++) cin >> s[i]; if (~n & 1) { cout << "NOT POSSIBLE\n"; return 0; } for (int i = 1; i <= n; i++) hsh[i] = hsh[i - 1] + H(s[i]); bool flag1 = false, flag2 = false; /* 1234567 */ int m = n / 2; for (int i = 1; i <= m; i++) { H t; t += hsh[i - 1]; t += (hsh[m + 1] - hsh[i]); if (t == (hsh[n] - hsh[m + 1])) flag2 = true; } for (int i = m + 1; i <= n; i++) { H t; t += hsh[i - 1] - hsh[m]; t += hsh[n] - hsh[i]; if (t == hsh[m]) flag1 = true; } if (flag1 && flag2) { if (hsh[m] != (hsh[n] - hsh[m + 1])) { cout << "NOT UNIQUE\n"; return 0; } } if (flag1) for (int i = 1; i <= m; i++) cout << s[i]; else { if (flag2) for (int i = m + 2; i <= n; i++) cout << s[i]; else cout << "NOT POSSIBLE"; } cout << '\n'; }

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

friends.cpp: In constructor 'H::H(char)':
friends.cpp:29:9: warning: 'H::len' will be initialized after [-Wreorder]
   29 |     int len;
      |         ^~~
friends.cpp:27:8: warning:   'H::ll H::h1' [-Wreorder]
   27 |     ll h1;
      |        ^~
friends.cpp:31:5: warning:   when initialized here [-Wreorder]
   31 |     H (char c) : len(1), h1(c), h2(c) {}
      |     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...