QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719659#5577. AlchemynickbelovWA 0ms3820kbC++203.4kb2024-11-07 06:54:492024-11-07 06:54:50

Judging History

你现在查看的是最新测评结果

  • [2024-11-07 06:54:50]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3820kb
  • [2024-11-07 06:54:49]
  • 提交

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; int ogln=n;

    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);
    if(start==-1)
        return void(cout << "0\n");

    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;
        }
    }
    ans = min(ans,ogln/2 + (ogln%2));
    cout << ans << '\n';
}

int main()
{
    //KING OF THE WORLD...... U.W.T.B
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    run();
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3580kb

input:

ioi

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

noi

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3520kb

input:

ctsc

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

fool

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

vetted

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

aa

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

ic

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

tlffohemdcncrfrxaqsbzcoyodvbxmhqukvfpahnakexcmacqa

output:

12

result:

ok single line: '12'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3748kb

input:

qrgld

output:

1

result:

ok single line: '1'

Test #10:

score: -100
Wrong Answer
time: 0ms
memory: 3600kb

input:

ejyfprguvwrnrsrykyrotmdjuzroohvlxqhvyeukkvmshtpczyyecpzhsqvkxueqvhlxldhofrzcjdhtotykgrsdnrnvuyrphyjy

output:

34

result:

wrong answer 1st lines differ - expected: '26', found: '34'