QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#719653 | #5577. Alchemy | nickbelov# | WA | 0ms | 3840kb | C++20 | 3.3kb | 2024-11-07 06:42:17 | 2024-11-07 06:42:18 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;
struct chash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
constexpr ll NN = 2e5, M = 1000000007, L = 20;
ll f1[NN], f2[NN];
ll inv(ll a, ll b=M) { return 1 < a ? b - inv(b % a, a) * b / a : 1; } // inv a mod b
ll choose(ll n, ll k) { return f1[n] * f2[k] % M * f2[n - k] % M; } // n choose k
void run()
{
string s; cin >> s; int n = len(s); int odd = n%2;
string a = s.substr(0,n/2);
string b = s.substr(n/2 + n%2);
ranges::reverse(a);
assert(len(a)==len(b));
n = len(a);
int ans = 0;
//compute the lengths of the runs that are neq
//we care about their parity
//consider the first one as even
//then do +1 for every odd
//minus one for pairs of adjacent odds
//bang ?
bool first_flag = false;
vector<ll> runs;
vll pos;
ll ln = 0; ll start = -1;
for(int i : rep(n)){
if(a[i]!=b[i]){
if(ln==0) start=i;
ln++;
if(i==0) first_flag=true;
} else if(ln){
pos.push_back(start),runs.push_back(ln),ln=0;
}
} if(ln) pos.push_back(start),runs.push_back(ln);
int sz = len(runs);
for(ll i : rep(sz)){
ll x = runs[i];
if(x%2 == 0) ans += x/2;
else{
ans += x/2 + x%2;
if(!(i==0 and first_flag)) ans++; //cuz the very first one isnt odd ? lol ?
}
}
for(int i : rep(1,sz)){
if(runs[i]%2 and (runs[i-1]%2) and pos[i-1]+runs[i-1]==pos[i]-1){
if(i==1 and first_flag) continue; //?
ans--;
runs[i]=0;
}
}
cout << ans << '\n';
}
int main()
{
//KING OF THE WORLD...... U.W.T.B
cin.tie(0);
ios_base::sync_with_stdio(false);
run();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3524kb
input:
ioi
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
noi
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
ctsc
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
fool
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
vetted
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
aa
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
ic
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
tlffohemdcncrfrxaqsbzcoyodvbxmhqukvfpahnakexcmacqa
output:
12
result:
ok single line: '12'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
qrgld
output:
1
result:
ok single line: '1'
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 3616kb
input:
ejyfprguvwrnrsrykyrotmdjuzroohvlxqhvyeukkvmshtpczyyecpzhsqvkxueqvhlxldhofrzcjdhtotykgrsdnrnvuyrphyjy
output:
34
result:
wrong answer 1st lines differ - expected: '26', found: '34'