oj.uz

Submission #863864

# Submission time Handle Problem Language Result Execution time Memory
863864 2023-10-21T09:27:17 Z catlover Palinilap (COI16_palinilap) C++14
17 / 100
 1000 ms 9048 KB 
// cre: Nguyen Hoang Hung - Train VOI 2024

#include <bits/stdc++.h>

#define int long long

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)

#define debug(x) { cerr << #x << " = "; cerr << (x) << endl; }
#define PR(a,n) { cerr << #a << " = "; FOR(_,1,n) cerr << a[_] << ' '; cerr << endl; }
#define PR0(a,n) { cerr << #a << " = "; REP(_,n) cerr << a[_] << ' '; cerr << endl; }

#define bit(X, i) ((X >> i) & 1)
#define cntbit(X) __builtin_popcountll(X)
#define fi first
#define se second
#define pb push_back
#define all(X) begin(X), end(X)
#define SZ(X) ((int)(X).size())
#define RR(X) X.resize(unique(all(X)) - begin(X))
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

using namespace std;

template <typename T>
bool maximize(T &x, T y)
{
  if(x < y)
    x = y;
  else
    return 0;
  return 1;
}
template <typename T>
bool minimize(T &x, T y)
{
  if(x > y)
    x = y;
  else
    return 0;
  return 1;
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

ll Rand(ll l, ll r) { return l + rand() % (r - l + 1); }

const int maxN = 1e6;
const ll inf = 1e18+7;
const int MOD = 1e9 + 7;
const double PI = acos(-1);
const int base = 31;

/*
-------------------------------------------------------------------------------------
    END OF TEMPLATE
-------------------------------------------------------------------------------------
    Nguyen Hoang Hung - catlover
    Training for VOI24 gold medal
-------------------------------------------------------------------------------------
*/

string S;
int N;
int Hash[maxN+5], rHash[maxN+5];
int pw[maxN+5];

void in()
{
    cin >> S;
    N = SZ(S);
}

int getHash(int l, int r, int H[maxN+5])
{
    return (H[r] - H[l - 1] * pw[r - l + 1] + 1ll * MOD * MOD) % MOD;
}

bool check_palin(int i, int j)
{
    int tmp1 = getHash(i, j, Hash);
    int tmp2 = getHash(N - j + 1, N - i + 1, rHash);
    return tmp1 == tmp2;
}

void init()
{
    string tmp = S;

    S = ' ' + S;
    reverse(all(tmp));
    tmp = ' ' + tmp;

    pw[0] = 1;
    Hash[0] = 0;
    rHash[0] = 0;

    FOR(i, 1, N)
    {
        Hash[i] = (Hash[i - 1] * base + S[i] - 'a') % MOD;
        rHash[i] = (rHash[i - 1] * base + tmp[i] - 'a') % MOD;
        pw[i] = pw[i - 1] * base % MOD;
    }
}

int calc()
{
    int res = 0;
    FOR(i, 1, N)
    {
        FOR(j, i, N)
        {
            if(check_palin(i, j)) ++res;
        }
    }
    return res;
}

void trau()
{
    string o = S;
    int ans = 0;
    FOR(i, 0, N - 1)
    {
        FOR(j, 0, 25)
        {
            S = o;
            S[i] = char(j + 'a');
            init();
            maximize(ans, calc());
        }
    }
    cout << ans;
}

void solve() {
    in();
    trau();
}

void solve_TestCase() {
  int testcase; cin >> testcase;

  while(testcase --> 0)
  {
    solve();
  }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);

    file("PALIVAL");

//    solve_TestCase();

    solve();

    cerr << "\nTime : " << clock()/1000.0 << "s\n";

    return 0;
}

Compilation message

palinilap.cpp: In function 'int32_t main()':
palinilap.cpp:24:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palinilap.cpp:158:5: note: in expansion of macro 'file'
  158 |     file("PALIVAL");
      |     ^~~~
palinilap.cpp:24:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
palinilap.cpp:158:5: note: in expansion of macro 'file'
  158 |     file("PALIVAL");
      |     ^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4692 KB Output is correct
2 Correct 47 ms 4444 KB Output is correct
3 Correct 48 ms 4548 KB Output is correct
4 Correct 47 ms 4444 KB Output is correct
5 Correct 47 ms 4444 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 4444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1039 ms 9048 KB Time limit exceeded
2 Halted 0 ms 0 KB -