QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#95784 | #5577. Alchemy | __# | WA | 2ms | 3484kb | C++14 | 3.2kb | 2023-04-11 21:48:51 | 2023-04-11 21:48:51 |
Judging History
answer
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define endl '\n'
#define int ll
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5+7, P1 = 31, P2 = 37, mod= 1e9 + 7;
int mul(int a, int b) {
return (1LL * a * b) % mod;
}
int add(int a, int b) {
a = (a + mod) % mod;
b = (b + mod) % mod;
return (a + b) % mod;
}
int fp(int b, int p) {
if (b == 1 or p == 0)
return 1;
int ret = fp(b, p >> 1);
ret = mul(ret, ret);
if (p & 1)
ret = mul(ret, b);
return ret;
}
ll modInv(ll n) {
return fp(n, mod - 2);
}
ll fact[N], inv[N];
void pre() {
fact[0] = inv[0] = 1;
for (ll i = 1; i < N; i++)
fact[i] = (fact[i - 1] * i) % mod, inv[i] = fp(fact[i], mod - 2);
}
ll nCr(ll n, ll r) {
return ((fact[n] * inv[r]) % mod * inv[n - r]) % mod;
}
ll nPr(ll n, ll r) {
return ((fact[n] * inv[n - r])) % mod;
}
void doWork() {
string s;
cin >> s;
int n = s.size();
vector<pair<int,int>> v;
for (int i = 0; i < n/2; ++i) {
if ( s[i] != s[n-1-i])
{
pair<int,int> p ={i,i};
while ((i+1)!= n/2 && (s[i+1] != s[n-1-(i+1)]))
{
i++;
}
p.second = i;
//cout << p.first << " " << p.second << endl;
v.push_back(p);
// return;
}
}
vector<pair<int,int>> fin;
for(auto &[i,j] : v)
{
if ((fin.size()) && (i == j || (fin.back().first == fin.back().second)))
{
// try to merge
int nw = 0;
if ( i == j)
{
if ( n-1-i -i <= 2)
nw = 1;
else nw = 2;
}
else
nw = (j-i+2)/2;
int old = 0;
if ( fin.back().first == fin.back().second)
{
if ( n-1-fin.back().first -fin.back().first <= 2)
old = 1;
else old = 2;
}
else
{
old = (fin.back().second-fin.back().first+2) / 2;
}
// merge
int merge = (j-fin.back().first +2)/2;
if ( merge < nw+old)
{
fin.back().second = j;
}
}
else
{
fin.push_back({i,j});
}
}
int ans =0;
for(auto &[i,j] : fin)
{
int nw = 0;
if ( i == j)
{
if ( n-1-i -i <= 2)
nw = 1;
else nw = 2;
}
else
nw = (j-i+2)/2;
ans+=nw;
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
// freopen("bisector.in","r",stdin);
// freopen("bisector.out","w",stdout);
int t = 1;
// cout << primes.size() << endl;
// cin >> t;
while (t--) {
doWork();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3392kb
input:
ioi
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
noi
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3444kb
input:
ctsc
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3480kb
input:
fool
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3480kb
input:
vetted
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3400kb
input:
aa
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
ic
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3428kb
input:
tlffohemdcncrfrxaqsbzcoyodvbxmhqukvfpahnakexcmacqa
output:
12
result:
ok single line: '12'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3436kb
input:
qrgld
output:
1
result:
ok single line: '1'
Test #10:
score: -100
Wrong Answer
time: 2ms
memory: 3420kb
input:
ejyfprguvwrnrsrykyrotmdjuzroohvlxqhvyeukkvmshtpczyyecpzhsqvkxueqvhlxldhofrzcjdhtotykgrsdnrnvuyrphyjy
output:
2
result:
wrong answer 1st lines differ - expected: '26', found: '2'