제출 #1076491

#제출 시각아이디문제언어결과실행 시간메모리
1076491vjudge1Necklace (Subtask 4) (BOI19_necklace4)C++17
0 / 15
3 ms600 KiB
#include<bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) #define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; --i) #define REP(i, a, b) for(int i = (a), _b = (b); i < _b; ++i) #define REPD(i, b, a) for(int i = (b), _a = (a); i > _a; --i) #define MASK(i) (1LL << (i)) #define BIT(mask, i) (((mask) >> (i)) & 1) #define __builtin_popcount __builtin_popcountll #define all(v) v.begin(), v.end() #define ll long long #define ull unsigned long long #define pii pair<int, int> #define pll pair<ll, ll> #define sz(v) (int)v.size() #define fi first #define se second mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll Rand(ll l, ll r) {return l + rng() % (r - l + 1);} template<class X, class Y> bool minimize(X &x, const Y &y) { if (x > y) { x = y; return true; } else return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { if (x < y) { x = y; return true; } else return false; } template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); } const int mod = 1e9 + 7; const int inf = 1e9; const int N = 3e3 + 5; int n, m; string s, t; int kmp[2][N]; void KMP(int pos, string s, string t) { s = s + '#' + t; kmp[pos][0] = 0; int j = 0; REP(i, 1, s.size()) { while(j > 0 && s[i] != s[j]) j = kmp[pos][j - 1]; if(s[i] == s[j]) ++j; kmp[pos][i] = j; } } void process() { cin >> s >> t; n = s.size(); m = t.size(); int res(0), ls(0), lt(0); REP(type, 0, 2) { reverse(all(s)); REP(i, 0, n - 1) { string tmp = s.substr(0, i + 1); reverse(all(tmp)); reverse(all(t)); KMP(0, tmp, t); reverse(all(t)); tmp = s.substr(i + 1, n - i - 1); KMP(1, tmp, t); REP(j, 0, m - 1) { if(maximize(res, kmp[0][i + m - j] + kmp[1][j + n - i])) { if(type == 0) ls = n - i - 1 - kmp[1][j + n - i]; else ls = i - kmp[0][i + m - j]; lt = j - kmp[1][j + n - i] + 1; } } } } cout << res << '\n'; cout << ls << ' ' << lt << '\n'; } signed main() { if(fopen("test.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int ntests = 1; // cin >> ntests; while(ntests--) process(); // cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s!\n"; return 0; }

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

necklace.cpp: In function 'int main()':
necklace.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...