oj.uz

답안 #437544

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
437544 2021-06-26T13:50:36 Z codebuster_10 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 334 ms 488 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t //be careful about this 
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)

#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound  
#define UB upper_bound
#define PQ priority_queue

#define SZ(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a, b, sizeof(a))

template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}


void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  // remove this when size of input is not fixed.
  cin.exceptions(cin.failbit); 
	cout.precision(15);	cout << fixed;
  if(SZ(s)){
  	freopen((s+".in").c_str(),"r",stdin);
  	freopen((s+".out").c_str(),"w",stdout);
  }
}




















namespace kmp {
  // Returns the next length to search from after starting from `len` and adding char `c`.
  // Runs in worst case O(len) but amortizes to O(1) in most situations.
  template<typename T, typename T_elem>
  int get_link(const T &pattern, const vector<int> &fail, int len, const T_elem &c) {
  	while(len > 0 && pattern[len] != c)	len = fail[len];
 		if(pattern[len] == c)	len++;
 		return len;
  }
 
  // Computes the failure function on `pattern` so that we can search for it in future strings.
  template<typename T>
  vector<int> compute_failure_function(const T &pattern) {
  	// fail[i] = for the prefix [0, i) of `pattern`, the length of the longest proper prefix that is also a suffix.
    int n = int(pattern.size());
    vector<int> fail(n + 1, 0);
    int len = 0;
 
    for(int i = 1; i < n; i++) {
    	len = get_link(pattern, fail, len, pattern[i]);
      fail[i + 1] = len;
    }
 
    return fail;
  }
}
 






const char DELIMITER = '#';


void solve(const string s,const string t, int& max_length, int& start_s, int& start_t, bool reversed_t){
	
	int n = SZ(s), m = SZ(t);
	
	string sa, sb;
	vt<int> va, vb;
	
	for(int i = 0; i <= n; ++i){
		sa.clear(); sb.clear();
		va.clear(); vb.clear();
		
		for(int j = i; j < n; ++j) sa.pb(s[j]);
		sa.pb(DELIMITER);
		sa += t;
		
		sb = t;
		sb.pb(DELIMITER);
		for(int j = 0; j < i; ++j) sb.pb(s[j]);
		
		reverse(all(sb));
		
		va = kmp::compute_failure_function(sa);
		vb = kmp::compute_failure_function(sb);
		
		int x = i, y = n - i;
		for(int j = 0; j <= m; ++j){
			int tmp = va[y+1+j] + vb[x+1+m-j];
			if(ckmax(max_length,tmp)){
				start_s = i - vb[x+1+m-j];
				start_t = j - va[y+1+j];
				if(reversed_t){
					int end_t = j + vb[x+1+m-j] - 1;
					start_t = m - 1 - end_t;
				}
			}
		}
	}
	return;
}


signed main(){
  setIO();
  string s,t;
  rd(s,t);
  
  int max_length = 0, start_s = -1, start_t = -1;

	solve(s,t,max_length,start_s,start_t,false);
	reverse(all(t));
  solve(s,t,max_length,start_s,start_t,true);
  
  cout << max_length << endl;
  cout << start_s << ' ' << start_t; 
}

Compilation message

necklace.cpp: In function 'void setIO(std::string)':
necklace.cpp:85:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |    freopen((s+".in").c_str(),"r",stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:86:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |    freopen((s+".out").c_str(),"w",stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 2 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 7 ms 308 KB Output is correct
7 Correct 6 ms 332 KB Output is correct
8 Correct 6 ms 332 KB Output is correct
9 Correct 6 ms 272 KB Output is correct
10 Correct 6 ms 332 KB Output is correct
11 Correct 8 ms 332 KB Output is correct
12 Correct 7 ms 332 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 7 ms 308 KB Output is correct
7 Correct 6 ms 332 KB Output is correct
8 Correct 6 ms 332 KB Output is correct
9 Correct 6 ms 272 KB Output is correct
10 Correct 6 ms 332 KB Output is correct
11 Correct 8 ms 332 KB Output is correct
12 Correct 7 ms 332 KB Output is correct
13 Correct 299 ms 472 KB Output is correct
14 Correct 281 ms 460 KB Output is correct
15 Correct 298 ms 464 KB Output is correct
16 Correct 334 ms 488 KB Output is correct
17 Correct 270 ms 468 KB Output is correct
18 Correct 279 ms 460 KB Output is correct
19 Correct 280 ms 472 KB Output is correct
20 Correct 282 ms 484 KB Output is correct
21 Correct 282 ms 468 KB Output is correct