Submission #37847639

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define _CRT_SECURE_NO_DEPRECATE
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define SYNC std::ios_base::sync_with_stdio(0); cout.tie(nullptr);
#define FRE freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
void __print(int x) {cerr << x;}
void __print(int32_t x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#define _CRT_SECURE_NO_DEPRECATE
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define SYNC std::ios_base::sync_with_stdio(0); cout.tie(nullptr);
#define FRE freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)

void __print(int x) {cerr << x;}
void __print(int32_t x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...) 42
#endif

const int MOD = 1e9 + 7;
const int MOD1 = 998244353;
const int N = 2e6 + 5;
const int INF = 1000111000111000111LL;
const long double EPS = 1e-12;
const long double PI = 3.141592653589793116;

const int mod_hash = 1e9+207;
const int p = 31;
const int p1 = 29;
const int mod_hash1 = 1e9+7;

int modular_exp(int base,int exp,int mod)
{
    int ans =1;
    while(exp)
    {
        if(exp%2)   ans = ans%mod*base%mod;
        base = (base%mod*base%mod)%mod;
        exp/=2;
        ans%=mod;
    }
    return ans;
}
int inverse_modulo(int base,int mod)
{
    return modular_exp(base,mod-2,mod);
}
int p_inv[N];
int p_inv1[N];


struct str_hash
{
    string s;
    vector<int> pre;
    vector<int> pre1;
    str_hash(string s) {
        this->s = s;
        compute_hash();
    }
    void compute_hash()
    {
        int hash_val = 0, hash_val1 = 0;
        int p_pow = 1;
        vector<int> pre_compute, pre_compute1;
        for(auto c : s) {
            hash_val = (hash_val + (c-'a'+1)*p_pow) % mod_hash;
            p_pow = (p_pow * p) % mod_hash;
            pre_compute.push_back(hash_val);
        }
        p_pow = 1;
        for(auto c : s) {
            hash_val1 = (hash_val1 + (c-'a'+1)*p_pow) % mod_hash1;
            p_pow = (p_pow * p1) % mod_hash1;
            pre_compute1.push_back(hash_val1);
        }
        this->pre = pre_compute;
        this->pre1 = pre_compute1;
    }
    pair<int, int> get_hash(int l, int r)
    {
    	if (l > r)
    		return {0, 0};
        if(l==0)    return {pre[r], pre1[r]};
        int res = (pre[r] - pre[l-1]+mod_hash)%mod_hash;
        res *= p_inv[l];
        int res1 = (pre1[r] - pre1[l-1]+mod_hash1)%mod_hash1;
        res1 *= p_inv1[l];
        return {res % mod_hash, res1 % mod_hash1};
    }
};

string get_str(string a, int l, int r) {
	return a.substr(l, r - l + 1);
}

void pre_all() {
	int inv = inverse_modulo(p,mod_hash);
    p_inv[0] = 1;
    for(int i = 1; i < N; i++) p_inv[i] = (inv * p_inv[i-1])%mod_hash;

    int inv1 = inverse_modulo(p1,mod_hash1);
    p_inv1[0] = 1;
    for(int i = 1; i < N; i++) p_inv1[i] = (inv1 * p_inv1[i-1])%mod_hash1; 
}

int32_t main() {
	SYNC
	pre_all();
	int n; cin >> n;
	string t; cin >> t;
	string rev_t = t;
	reverse(rev_t.begin(), rev_t.end());

	str_hash f_hash(t);
	str_hash b_hash(rev_t);
	// debug(f_hash.get_hash(0, 2), b_hash.get_hash(1, 3));
	for (int i = 0; i < n; i++) {
		bool match = true;
		if (f_hash.get_hash(0, i) != b_hash.get_hash(n - i - 1, n - 1))
			match = false;
		if (i == 1) {
			debug(get_str(t, 0, i), get_str(rev_t, n - i - 1, n - 1), match);
		}
		if (f_hash.get_hash(i + n + 1, 2 * n - 1) !=  b_hash.get_hash(n, 2 * n - i - 2))
			match = false;
		// if (i == 1) {
		// 	debug(f_hash.get_hash(i + n + 1, 2 * n - 1));
		// 	debug(b_hash.get_hash(n, 2 * n - i - 2));
		// 	debug(get_str(t, i + n + 1, 2 * n - 1), get_str(rev_t, n, 2 * n - i - 2), match);
		// }
		if (match) {
			string res = t.substr(i + 1, n);
			reverse(res.begin(), res.end());
			cout << res << '\n' << i + 1;
			return 0;
		}
	}
	int all_match = 0;
	int rt = 2 * n - 1;
	for (int i = n - 1; i >= 0; i--) {
		if (t[i] == t[rt])
			all_match++;
		rt--;
	}
	if (all_match == n) {
		cout << t.substr(n, n) << '\n' << 0;
	}
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int32_t main()’:
./Main.cpp:29:21: warning: statement has no effect [-Wunused-value]
   29 | #define debug(x...) 42
      |                     ^~
./Main.cpp:135:4: note: in expansion of macro ‘debug’
  135 |    debug(get_str(t, 0, i), get_str(rev_t, n - i - 1, n - 1), match);
      |    ^~~~~

Judge Result